学步园

不明白可以去看Matrix大神的矩阵的十种应用去

code：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 31;

int city_num,city[MAXN];

struct Mat
{
	int mat[MAXN][MAXN];
}A,E;

Mat operator+ (Mat a,Mat b)
{
	Mat res;
	int i,j;
	for (i=1;i<=city_num;i++)
	{
		for(j=1;j<=city_num;j++)
			res.mat[i][j] = ( a.mat[i][j] + b.mat[i][j] )%2008 ;
	}
	return res;
}

Mat operator* (Mat a,Mat b)
{
	int i,j,k;
	Mat res;
	for (i=1;i<=city_num;i++)
	{
		for (j=1;j<=city_num;j++)
		{
			res.mat[i][j] = 0;
			for(k=1;k<=city_num;k++)
				res.mat[i][j]=( res.mat[i][j] + a.mat[i][k]*b.mat[k][j] ) % 2008;
		}
	}
	return res;
}

Mat operator^ (Mat a,int exp)
{
	Mat res = E, tmp = a;
	while(exp)
	{
		if(exp&1)
			res = res * tmp;
		exp >>= 1;
		tmp = tmp * tmp;
	}
	return res;
}

int GetCity(int x)
{
	int i;
	for (i=1;i<=city_num;i++)
	{
		if(city[i]==x)
			return i;
	}
    city[++city_num] = x;
    return city_num;
}

Mat GetSum(Mat a,int k)
{
	if(k==1)
		return a;
	if(k&1)
		return (a^k) + GetSum(a,k-1);
    return ((a^(k>>1))+E) * GetSum(a,k>>1);
}
int main()
{
	int a,b,c,d;
	int i,j,n,k,sum;
	Mat tem1,tem2;
	for(i=1;i<=30;i++)
		for(j=1;j<=30;j++)
			E.mat[i][j] = (i==j);
	while (scanf("%d",&n)!=EOF)
	{
		city_num = 0;
		memset(city,-1,sizeof(city));
		memset(A.mat,0,sizeof(A.mat));
		while (n--)
		{
			scanf("%d%d",&a,&b);
			a = GetCity(a);
			b = GetCity(b);
			A.mat[a][b]++;
		}
		scanf("%d",&k);
		while (k--)
		{
			scanf("%d%d%d%d",&a,&b,&c,&d);
			if(c>d) swap(c,d);

			a = GetCity(a);
			b = GetCity(b);

			if( c==0&&d==0 || a==-1 || b==-1) puts("0");
			else{
				if (c>1)
                    printf("%d\n",((GetSum(A,d).mat[a][b]-GetSum(A,c-1).mat[a][b])+2008)%2008);
				else
                    printf("%d\n",GetSum(A,d).mat[a][b]);
			}
		}
	}
	return 0;
}