3802842_ac_1469ms_7956k.cpp

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

#include <stdio.h>
#include <string.h>
#pragma comment(linker, "/STACK:16777216")

int m, k;

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

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

	for(i = 0; i < k; i++)
	{
		for(j = 0; j < k; j++)
		{
			t.num[i][j] = 0;
			for(l = 0; l < k; l++)
			{
				t.num[i][j] += a.num[i][l] * b.num[l][j];
				t.num[i][j] %= 10000;
			}
			t.num[i][j] %= 10000;
		}
	}
	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 i, j, q;
	int num[200];

	while (scanf("%d", &k) == 1)
	{
		if (k == 0)
			break;
		memset(b.num,0,sizeof(b.num));
		for (i = 0; i < k; i++)
		{
			scanf("%d", &num[i]);
		}
		for (i = 0; i < k; i++)
		{
			scanf("%d", &b.num[i][0]);
			if (i != k - 1)
			{
				b.num[i][i + 1] = 1;
			}
		}
		for (i = k; i < k * 2 - 1; i++)
		{
			num[i] = 0;
			for (j = 1; j <= k; j++)
			{
				num[i] += num[i - j] * b.num[j - 1][0];
				num[i] %= 10000;
			}
		}
		scanf("%d", &i);
		if (i < k * 2 - 1)
		{
			printf("%d\n", num[i]);
			continue;
		}
		int n = i;
		for (i = k - 1; i >= 0; i--)
		{
			for (j = k - 1, q = k - i - 1; j >= 0; j--, q++)
			{
				a.num[i][j] = num[q];
			}
		}
		int Ans = multi(a, power(b ,n - k * 2 + 2)).num[0][0] % 10000;
		if(Ans < 0)
		{
			Ans += 10000;
		}
		printf("%d\n",Ans);
	}
	return 0;
}