gauss fibonacci.cpp

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

#include <cstdio>
#include <memory>

using namespace std;

#define SIZE 5

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

mat I;
int M;

mat mult(mat x, mat y, int n)
{
	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]) % M;
		}
	return c;
}

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

mat spow(mat a, int k, int n)//sum of I + a ^ 1 + a ^ 2 + a ^ 3 + ... + a ^ (k - 1), size = n;
{
	mat p, s;
	memset(p.d, 0, sizeof(p.d));
	memset(s.d, 0, sizeof(s.d));
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++) p.d[i][j] = a.d[i][j];
	for(int i = 1; i <= n; i++)
	{
		p.d[i][i + n] = 1;
		p.d[i + n][i + n] = 1;
	}
	p = powx(p, k, 2 * n);
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			s.d[i][j] = p.d[i][j + n];
	return s;
}

int main(void)
{
	int k, b, n;
	mat p, a;
	for(int i = 1; i <= SIZE - 1; i++) I.d[i][i] = 1;
	while(scanf("%d %d %d %d", &k, &b, &n, &M) != EOF)
	{
		memset(a.d, 0, sizeof(a.d));
		a.d[1][1] = a.d[1][2] = a.d[2][1] = 1;
		a.d[2][2] = 0;
		p = mult(powx(a, b, 2), spow(powx(a, k, 2), n, 2), 2);
		printf("%I64d\n", p.d[1][2]);
	}
	return 0;
}