奥运
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2252 Accepted Submission(s): 573
Problem Description
北京迎来了第一个奥运会，我们的欢呼声响彻中国大地，所以今年的奥运金牌 day day up!
比尔盖兹坐上鸟巢里，手里摇着小纸扇，看的不亦乐乎，被俺们健儿的顽强拼搏的精神深深的感动了。反正我的钱也多的没地方放了，他对自己说，我自己也来举办一个奥运会，看谁的更火。不过他的奥运会很特别：
1 参加人员必须是中国人；
2 至少会加法运算（因为要计算本人获得的金牌数）
他知道中国有很多的名胜古迹，他知道自己在t1 到 t2天内不可能把所有的地方都玩遍，所以他决定指定两个地方v1,v2，如果参赛员能计算出在t1到t2天（包括t1,t2）内从v1到v2共有多少种走法(每条道路走需要花一天的时间，且不能在某个城市停留,且t1=0时的走法数为0)，那么他就会获得相应数量的金牌，城市的总数<=30,两个城市间可以有多条道路
，每条都视为是不同的。
比尔盖兹坐上鸟巢里，手里摇着小纸扇，看的不亦乐乎，被俺们健儿的顽强拼搏的精神深深的感动了。反正我的钱也多的没地方放了，他对自己说，我自己也来举办一个奥运会，看谁的更火。不过他的奥运会很特别：
1 参加人员必须是中国人；
2 至少会加法运算（因为要计算本人获得的金牌数）
他知道中国有很多的名胜古迹，他知道自己在t1 到 t2天内不可能把所有的地方都玩遍，所以他决定指定两个地方v1,v2，如果参赛员能计算出在t1到t2天（包括t1,t2）内从v1到v2共有多少种走法(每条道路走需要花一天的时间，且不能在某个城市停留,且t1=0时的走法数为0)，那么他就会获得相应数量的金牌，城市的总数<=30,两个城市间可以有多条道路
，每条都视为是不同的。
Input
本题多个case，每个case：
输入一个数字n表示有n条道路 0<n<10000
接下来n行每行读入两个数字 p1，p2 表示城市p1到p2有道路，并不表示p2到p1有道路 (0<=p1,p2<2^32)
输入一个数字k表示有k个参赛人员
接下来k行，每行读入四个数据v1,v2,t1,t2 (0<=t1,t2<10000)
输入一个数字n表示有n条道路 0<n<10000
接下来n行每行读入两个数字 p1，p2 表示城市p1到p2有道路，并不表示p2到p1有道路 (0<=p1,p2<2^32)
输入一个数字k表示有k个参赛人员
接下来k行，每行读入四个数据v1,v2,t1,t2 (0<=t1,t2<10000)
Output
对于每组数据中的每个参赛人员输出一个整数表示他获得的金牌数（mod 2008）
Sample Input
6 1 2 1 3 2 3 3 2 3 1 2 1 3 1 2 0 0 1 2 1 100 4 8 3 50
Sample Output
0 1506 0HDOJ 2254 矩阵应用 题意：有向图中求A点到B点路径长度为t1~t2的路径总数 离散数学中，有向图的邻接矩阵A表示所有点之间路径长度为1的路径数量， A^n则表示路径长度为n的路径数量，故需要求某两点在(A^t1)~(A^t2)的路径数量之和
#include<iostream>
#include<stdio.h>
#include<map>
using namespace std;
#define N 31
#define M 2008
struct matrix{
int map[N][N];
};
matrix mat[10001];
map<int,int>mp;
int len;
matrix multi(matrix &a,matrix &b)
{
matrix temp;
int i,j,k;
for(i=0;i<len;i++)
for(j=0;j<len;j++)
{
temp.map[i][j]=0;
for(k=0;k<len;k++)
temp.map[i][j]+=a.map[i][k]*b.map[k][j];
temp.map[i][j]%=M;
}
return temp;
}
int main()
{
int n,i,j,a,b,t1,t2,v1,v2,ans,k;
//freopen("test.txt","r",stdin);
while(scanf("%d",&n)!=EOF)
{
memset(mat[0].map,0,sizeof(mat[0].map));//最初的矩阵
mp.clear();
len=0;
for(i=0;i<n;i++)
{
scanf("%d%d",&a,&b);
if(mp.find(a)==mp.end())//当前点的序号 以这些点 建图
mp[a]=len++;
if(mp.find(b)==mp.end())
mp[b]=len++;
mat[0].map[mp[a]][mp[b]]++;
}
for(i=1;i<10001;i++)
mat[i]=multi(mat[i-1],mat[0]);//矩阵相乘 mat[i]矩阵的多少次幂
scanf("%d",&k);
while(k--)
{
scanf("%d%d%d%d",&v1,&v2,&t1,&t2);
if(mp.find(v1)==mp.end()||mp.find(v2)==mp.end()||t1==0&&t2==0)
{
printf("0\n");
continue;
}
ans=0;
for(i=t1-1;i<t2;i++)
ans+=mat[i].map[mp[v1]][mp[v2]];
printf("%d\n",ans%M);
}
}
return 0;
}