HDU 2254 奥运 Matrix Power
如果 a 到 b 有路，则map[a][b] = 1，否则map[a][b] = 0，譬如如果1→3，1→4，2→1，2→3，3→4，4→2，4→3有路，则可以构造矩阵：
矩阵的k次方表示这个矩阵走了k步。
所以k天后就算矩阵的k次方。
这样就变成：初始矩阵的^[t1,t2]这个区间内的v[v1][v2]的和。
所以就是二分等比序列求和上场的时候了。
跟HDU 1588 Gauss Fibonacci的算法一样。
Also check http://alanyume.com/97.html
Please read full article from HDU 2254 奥运 Matrix Power
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 0
这样构造好矩阵之后，如果求从 1 到 2 走 5 天（每条路走一天），有几条路，就可以这样计算：
结果中，第 n 行第 m 列就是 n 到 m 要走 5 天的路数。
一张有向图的邻接矩阵A，A表示所有点之间路径长度为一的路径数量，A^n则表示路径长度为n的路径数量，故需要求某两点在(A^t1)~(A^t2)的路径数量之和矩阵的k次方表示这个矩阵走了k步。
所以k天后就算矩阵的k次方。
这样就变成：初始矩阵的^[t1,t2]这个区间内的v[v1][v2]的和。
所以就是二分等比序列求和上场的时候了。
跟HDU 1588 Gauss Fibonacci的算法一样。
struct Matrix { int mat[N][N]; int n, m; Matrix() {//初始化 n = m = N; memset(mat, 0, sizeof(mat)); } inline void init(int row, int column) {//初始矩阵大小 n = row, m = column; } void init_e() {//单位矩阵 for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { mat[i][j] = (i == j); } } }}; //加法Matrix operator + (Matrix a, Matrix b) { Matrix ret; ret.init(a.n, a.m); for (int i = 0; i < a.n; i++) { for (int j = 0; j < a.m; j++) { ret.mat[i][j] = a.mat[i][j] + b.mat[i][j]; if (ret.mat[i][j] >= mod) { ret.mat[i][j] %= mod; } } } return ret;} //n行m列 * m行p列 = n行p列Matrix operator * (Matrix a, Matrix b) { Matrix ret; ret.init(a.n, b.m); for (int i = 0; i < a.n; i++) { for (int k = 0; k < a.m; k++) if (a.mat[i][k]) { for (int j = 0; j < b.m; j++) if (b.mat[k][j]) { ret.mat[i][j] = ret.mat[i][j] + a.mat[i][k] * b.mat[k][j]; if (ret.mat[i][j] >= mod) { ret.mat[i][j] %= mod; }//if }//for(j) }//for(k) }//for(i) return ret;}//求幂一般都是正方形矩阵，所以ret = a;Matrix operator ^ (Matrix a, int b) { Matrix ret = a, tmp = a; ret.init_e(); for ( ; b; b >>= 1) { if (b & 1) { ret = ret * tmp; } tmp = tmp * tmp; } return ret;}//递归幂求和//用二分法求矩阵和,递归实现 Matrix Power_Sum1(Matrix a, int b) { Matrix ret = a; ret.init_e(); if (b == 1) { return a; } else if (b & 1) { return (a ^ b) + Power_Sum1(a, b - 1); } else { return Power_Sum1(a, b >> 1) * ((a ^ (b >> 1)) + ret); }}//非递归幂求和Matrix Power_Sum2(Matrix a, int b) { int k = 0 ,ss[32]; Matrix tp1, tp2, ret; tp1 = tp2 = ret = a; ret.init_e(); while (b) { ss[k++] = b & 1; b >>= 1; } for (int i = k - 2; i >= 0; i--) { tp1 = tp1 * (tp2 + ret); tp2 = tp2 * tp2; if (ss[i]) { tp2 = tp2 * a; tp1 = tp1 + tp2; } } return tp1;}int main(void) { int cas, n; int v1, v2, t1, t2, x, y; while (~scanf("%d", &cas)) { map <int, int> mp;//最多只有30条路，所以用map映射 mp.clear(); Matrix a, b, c; int cnt = 1; for (int i = 0; i < cas; i++) { scanf("%d %d", &x, &y); if (!mp[x]) { mp[x] = cnt++; } if (!mp[y]) { mp[y] = cnt++; } a.mat[mp[x]][mp[y]] ++; } a.init(cnt, cnt); // a.print(); b.init(cnt, cnt); c.init(cnt, cnt); scanf("%d", &n); while (n--) { scanf("%d%d%d%d", &v1, &v2, &t1, &t2); x = mp[v1]; y = mp[v2]; if (x == 0 || y == 0 || (t1 == 0 && t2 == 0)) { puts("0"); continue; } int sum; if (t1 <= 1) { b = Power_Sum2(a, t2); // b.print(); sum = b.mat[x][y] % mod; printf("%d\n",sum); continue; } b = Power_Sum2(a, t2); c = Power_Sum2(a, t1 - 1); sum = (b.mat[x][y] % mod - c.mat[x][y] % mod + mod) % mod; printf("%d\n", sum); }//while(n) }//while(cas) return 0;}Please read full article from HDU 2254 奥运 Matrix Power
