3048052_wa.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>

int m;
struct node
{
	int num[4][4];
}b, a;

int ans[] = {0,1,5,11,36,95,281,781};

node multi(node a,node b)
{
	int i, j, k;
	node t;

	for(i = 0; i < 4; i++)
	{
		for(j = 0; j < 4; j++)
		{
			t.num[i][j] = 0;
			for(k = 0; k < 4; k++)
			{
				t.num[i][j] += a.num[i][k]*b.num[k][j];
				t.num[i][j] %= m;
			}
			t.num[i][j] %= m;
		}
	}
	return t;
}

node power(node t,int n)
{
	if(n==1)
	{
		return t;
	}
	if(n % 2==1)
	{
		return multi(power(t,n-1),t);
	}
	else
	{
		return power(multi(t,t),n/2);
	}
}

int main()
{
	int n;

	memset(b.num,0,sizeof(b.num));
	b.num[0][0] = 1;b.num[1][0] = 5;b.num[2][0] = 1;b.num[3][0] = -1;
	b.num[0][1] = b.num[1][2] = b.num[2][3] = 1;
	a.num[0][0] = ans[7];a.num[0][1] = ans[6];a.num[0][2] = ans[5];a.num[0][3] = ans[4];
	a.num[1][0] = ans[6];a.num[1][1] = ans[5];a.num[1][2] = ans[4];a.num[1][3] = ans[3];
	a.num[2][0] = ans[5];a.num[2][1] = ans[4];a.num[2][2] = ans[3];a.num[2][3] = ans[2];
	a.num[3][0] = ans[4];a.num[3][1] = ans[3];a.num[3][2] = ans[2];a.num[3][3] = ans[1];
	while(scanf("%d%d",&n,&m)==2,n)
	{
		if(n <= 7)
		{
			printf("%d\n",ans[n]%m);
		}
		else
		{
			int Ans = multi(a,power(a,n-7)).num[0][0]%m;
			if(Ans < 0)
			{
				Ans += m;
			}
			printf("%d\n",Ans);
		}
	}
	return 0;
}