magic bean(矩阵二分).cpp

杭电acm解题报告2001---2099.

#include <stdio.h>
#include <memory.h>
int A[30],B[30];
int T[30][30],T1[30][30],T2[30][30];
int n,m,t;

void solve()
{
	int i,j,k;

	for(i = 0;i <= n;i++)
		T1[i][i] = 1;

	memcpy(T2,T,sizeof(T));

	while(t)
	{
		if(t%2 == 1)
		{
			for(i = 0;i <= n;i++)
			{
				for(j = 0;j <= n;j++)
				{
					T[i][j] = 0;
					for(k = 0;k <= n;k++)
					{
						T[i][j] += T1[i][k]*T2[k][j];
						T[i][j] %= 2007;
					}
				}
			}

			memcpy(T1,T,sizeof(T));
		}
		t /= 2;
		for(i = 0;i <= n;i++)
		{
			for(j = 0;j <= n;j++)
			{
				T[i][j] = 0;
				for(k = 0;k <= n;k++)
				{
					T[i][j] += T2[i][k]*T2[k][j];
					T[i][j] %= 2007;
				}
			}
		}
		memcpy(T2,T,sizeof(T));
	}

	for(i = 0;i <= n;i++)
		for(k = 0;k <= n;k++)
		{
			B[i] += A[k] * T1[k][i];
			B[i] %= 2007;
		}
}

int main()
{
	int x,y,sum,i;
	while(scanf("%d %d",&n,&m))
	{
		if(n == 0 && m == 0) break;
		memset(B,0,sizeof(B));
		memset(T1,0,sizeof(T1));
		memset(T2,0,sizeof(T2));
		memset(T,0,sizeof(T));
		memset(A,0,sizeof(A));
		A[0] = 1;

		for(i = 0;i <= n;i++)
		{
			T[i][i] = 1;
			T[i][n] = 1;
		}
		for(i = 0;i < m;i++)
		{
			scanf("%d %d",&x,&y);
			x--;
			y--;
			T[x][y] = 1;
			T[y][x] = 1;
		}

		scanf("%d",&t);

		solve();

		sum = 0;
		for(i = 0;i <= n;i++)
		{
			sum += B[i];
			sum %= 2007;
		}

		printf("%d\n",sum);

	}
	return 0;
}