1128(矩阵幂).cpp

数值计算的例子和参考书籍

#include <stdio.h>
#include <memory.h>

#define P 1985
#define SIZE 71

typedef struct
{
	int d[SIZE][SIZE];
}mat;

int k, n;

mat mult(mat x, mat y)
{
	mat c;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
		{
			c.d[i][j] = 0;
			for(int t = 1; t <= n; t++)
				c.d[i][j] = (c.d[i][j] + x.d[i][t] * y.d[t][j]) % P;
		}
	return c;
}

mat powx(mat p, int x)
{
	if(x == 1) return p;
	mat sq = mult(p, p);
	return x % 2 == 0 ? powx(sq, x / 2) : mult(powx(sq, x / 2), p);
}

int main(void)
{
	mat p, a;
	while(scanf("%d %d", &n, &k) != EOF)
	{
		memset(p.d, 0, sizeof(p.d));
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++)
				scanf("%d", &p.d[i][j]);
		for(int i = 1; i <= n; i++)
		{
			p.d[i][i + n] = 1;
			p.d[i + n][i + n] = 1;
		}
		n *= 2;
		a = powx(p, k + 1);
		int sum = 0;
		n /= 2;
		for(int i = 1; i <= n; i++)
			for(int j = n + 1; j <= 2 * n; j++) sum = (sum + a.d[i][j]) % P;
		sum = (sum + 1985 - n) % P;
		printf("%d\n", sum);
	}
	return 0;
}