http://acm.tju.edu.cn/toj/showp2871.html
2871. Magic Bean
--------------------------------------------------------------------------------
Time Limit: 1.0 Seconds Memory Limit: 65536K
Total Runs: 15 Accepted Runs: 6
--------------------------------------------------------------------------------
The Reactivity Of Bean Association (ROBA) are making research on a special kind of bean. They draw a graph, and put a bean on node No.1. Then at each unit time, the bean will jump to an adjacent node or stay still. What's more, the bean may explode and disappear at some time.
Now the researchers want to know, given the graph and the time, how many different kinds of behavior will come up. For the answer may be very large, they only want to know the result % 2007.
Please note that the bean is always at Node 1 initially.
Input
The first line of each test case contains two integers N, M, (1 ≤ N ≤ 20, 0 ≤ M ≤ 100) indicating the number of nodes and edges in the graph. Then each of the following M lines contains two integers A and B (A ≠ B, 1 ≤ A,B ≤ N), indicating node A and node B are adjacent in the graph. You can assume all the (A, B) pairs in the input are different. The last line of each test case contains the observation time T (1 ≤ T ≤ 10^6).
The input are terminated by N = M = 0.
Output
Output the number of different ways mod 2007.
Sample Input
3 2
1 2
2 3
2
0 0
Sample Output
8
Hint
For the sample, all the ways are:
1->explode
1->1->explode
1->2->explode
1->1->1 (Observation ends)
1->1->2 (Observation ends)
1->2->1 (Observation ends)
1->2->2 (Observation ends)
1->2->3 (Observation ends)
这题我使用动态规划但是会超时，主要T的范围太大了，有什么更好的方法吗？
下面是我超时的代码
程序代码：
#include <iostream>using namespace std;
int* arr1;
int* arr2;int map[21][21];
int main()
{
int N,M,T;
arr1=new int[21];
arr2=new int[21];
while(scanf(\"%d%d\",&N,&M)!=EOF && (N||M)){memset(map,0,sizeof(map));
memset(arr1,0,21*sizeof(int));
memset(arr2,0,21*sizeof(int));
for(int i=0;i<M;i++){
int a,b;
scanf(\"%d%d\",&a,&b);
map[a][b]=map[b][a]=1;
}
for(int i=1;i<=N;i++){
map[i][i]=1;
}
scanf(\"%d\",&T);
for(int j=0;j<=N;j++){
arr1[j]=1;
}
for(int i=1;i<=T;i++){
for(int j=1;j<=N;j++){
arr2[j]=1;
for(int k=1;k<=N;k++){
if(map[j][k]){
arr2[j]=(arr2[j]+arr1[k])%2007;
}
}
}
swap(arr1,arr2);
}
printf(\"%d\n\",arr2[1]);
}
}
[此贴子已经被作者于2007-7-28 22:39:01编辑过]
