Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2926 Accepted Submission(s): 739
定义：设G=<V, E>是一个简单图，它有n个结点V={v1, v2, ... , vn }，则n阶方阵A(G)=(aij)称为G的邻接矩阵。其中
adj表示邻接，nadj表示不邻接。
定理：设A(G)是图G的邻接矩阵，则(A(G))k 中的i行，j列元素aij(k)等于G中联结vi与vj的长度为k的路的数目。证明见《离散数学》左孝凌。
求第t天城市 i 到城市 j 共有多少种走法就是求城市 i 到城市 j 经过1~k条道路的路径方案数，
设第t天方案数为B(t)，A为城市的邻接矩阵，有
那么t1到t2天（包括t1,t2）内从v1到v2的走法数目为B(t2)-B(t1-1),t1=0时特殊处理一下。
题意不是很明朗，需要注意的有
1. 城市的编号很大，但总数目<=30，要对城市重新编号。
2. 城市之间可能有重边。
3. B(t2)-B(t1-1)的结果可能小于零。
方法一：分块矩阵
建立下面分块矩阵，
各个分块均为m*m的(m为城市个数)，I为单位矩阵，O为零矩阵。
进一步得到，
运用矩阵快速幂进行求解，
1 #include <iostream> 2 #include <algorithm> 3 #include <map> 4 #include <vector> 5 #include <functional> 6 #include <string> 7 #include <cstring> 8 #include <queue> 9 #include <set> 10 #include <cmath> 11 #include <cstdio> 12 using namespace std; 13 #define IOS ios_base::sync_with_stdio(false) 14 typedef long long LL; 15 const int INF = 0x3f3f3f3f; 16 17 const int modnum = 2008; 18 const int maxn = 61; 19 typedef struct matrix{ 20 int v[maxn][maxn]; 21 void init(){ memset(v, 0, sizeof(v)); } 22 }M; 23 M a, b, c, z, bn1, bn2, res1, res2; 24 25 M mul_mod(const M &a, const M &b, int L, int m, int n) 26 { 27 M c; c.init(); 28 for (int i = 0; i<L; i++){ 29 for (int j = 0; j<n; j++){ 30 for (int k = 0; k<m; k++)//注意j，k范围 31 c.v[i][j] = (c.v[i][j] + (a.v[i][k] * b.v[k][j] % modnum)) % modnum; 32 } 33 } 34 return c; 35 } 36 M power(M x, int L, int p) 37 { 38 M tmp; tmp.init(); 39 for (int i = 0; i<L; i++) 40 tmp.v[i][i] = 1; 41 while (p){ 42 if (p & 1) tmp = mul_mod(x, tmp, L, L, L); 43 x = mul_mod(x, x, L, L, L); 44 p >>= 1; 45 } 46 return tmp; 47 } 48 inline void init(int n) 49 { 50 b.init(); 51 for (int i = 0; i<n; i++) 52 b.v[i][i] = b.v[i][i + n] = 1; 53 c.init(); 54 for (int i = 0; i<n; i++) 55 for (int j = 0; j<n; j++) 56 b.v[i + n][j + n] = c.v[i + n][j] = a.v[i][j]; 57 z.init(); 58 } 59 int main() 60 { 61 int n, t1, t2, k, cnt, ans; 62 LL p1, p2; 63 map<LL, int> cm; 64 while (~scanf("%d", &n)){ 65 cm.clear(); 66 a.init(); 67 cnt = 0; 68 for (int i = 0; i<n; i++){ 69 scanf("%lld%lld", &p1, &p2); 70 if (!cm.count(p1)) cm[p1] = cnt++; 71 if (!cm.count(p2)) cm[p2] = cnt++; 72 a.v[cm[p1]][cm[p2]]++; 73 } 74 int num = cm.size(); 75 init(num); 76 scanf("%d", &k); 77 for (int i = 0; i<k; i++){ 78 scanf("%lld%lld%d%d", &p1, &p2, &t1, &t2); 79 if (t1>t2) swap(t1, t2); 80 if (!cm.count(p1) || !cm.count(p2)){ printf("0\n"); continue; } 81 if(t1==0) res1=z;//z为零矩阵 82 else{ 83 bn1 = power(b, 2 * num, t1 - 1); 84 res1 = mul_mod(bn1, c, 2 * num, 2 * num, num); 85 } 86 if(t2==0) res2=z; 87 else{ 88 res2 = power(b, 2 * num, t2); 89 res2 = mul_mod(res2, c, 2 * num, 2 * num, num); 90 } 91 /* 92 因为t1<=t2 93 利用t1计算得到的结果在t2的结果，理想中可能会快一些 94 但测评系统运行时间仍然和直接计算t2一样 95 else if(t1!=0){ 96 bn2 = power(b, 2 * num, t2-t1+1); 97 bn2 = mul_mod(bn1, bn2, 2 * num, 2 * num, 2 * num); 98 res2 = mul_mod(bn2, c, 2 * num, 2 * num, num); 99 }else{ 100 bn2 = power(b, 2 * num, t2); 101 res2 = mul_mod(bn2, c, 2 * num, 2 * num, num); 102 } 103 */ 104 ans = (res2.v[cm[p1]][cm[p2]] - res1.v[cm[p1]][cm[p2]])%modnum; 105 while (ans<0) ans+=modnum; 106 printf("%d\n", ans%modnum); 107 } 108 } 109 }
方法二
原文：http://www.cnblogs.com/cumulonimbus/p/5698434.html
