POJ 3735 Training little cats 矩阵二分幂 + 矩阵优化
来源：http://poj.org/problem?id=3735
题意：有一些猫，这些猫可以获得一些花生，有三种操作：某只猫可以获得一个花生；某只猫花生变为0；两只猫的花生数目交换。问经过k次交换，且k次交换循环m次之后，每只猫有多少花生。
思路：因为猫的数量不多（<= 100），所以，可以用矩阵做，每种操作对应一个矩阵，矩阵相乘即可。循环m次即是矩阵的m次方，可以用矩阵二分幂。还有就是矩阵 乘法的优化，只有这样才可过。
矩阵乘法优化：
#include <iostream>#include <cstdio>#include <string.h>using namespace std;typedef long long LL;const int N = 110;int n,m,k;LL initm[N][N],addm[N][N],zerom[N][N],exchm[N][N],dd[N][N];void init(){memset(initm,0,sizeof(initm));for(int i = 0; i <= n; ++i){ initm[i][i] = 1;}}void add(int x){memset(addm,0,sizeof(addm));for(int i = 0; i <= n; ++i)addm[i][i] = 1;addm[n][x-1] = 1;}void zero(int x){memset(zerom,0,sizeof(zerom));for(int i = 0; i <= n; ++i)zerom[i][i] = 1;zerom[x-1][x-1] = 0;}void exch(int x,int y){memset(exchm,0,sizeof(exchm));for(int i = 0; i <= n; ++i)exchm[i][i] = 1;exchm[x-1][x-1] = 0;exchm[y-1][y-1] = 0;exchm[y-1][x-1] = 1;exchm[x-1][y-1] = 1;}void mult(LL mm[N][N],LL temp[N][N]){LL newmm[N][N];memset(newmm,0,sizeof(newmm));for(int i = 0; i <= n; ++i){for(int j = 0; j <= n; ++j){if(mm[i][j] == 0) continue;for(int k = 0; k <= n; ++k){ newmm[i][k] += mm[i][j] * temp[j][k];}}}memset(mm,0,sizeof(mm));for(int i = 0; i <= n; ++i){ for(int j = 0; j <= n; ++j) mm[i][j] = newmm[i][j];}}void mult2(int x){LL newmm[N][N];memset(newmm,0,sizeof(newmm));for(int i = 0; i <= n; ++i){for(int j = 0; j <= n; ++j){if(initm[i][j] == 0)continue;for(int k = 0; k <= n; ++k){ newmm[i][k] += initm[i][j] * initm[j][k];}}}for(int i = 0; i <= n; ++i){ for(int j = 0; j <= n; ++j) initm[i][j] = newmm[i][j];}if(x){ LL mm[N][N]; memset(mm,0,sizeof(mm)); for(int i = 0; i <= n; ++i){for(int j = 0; j <= n; ++j){if(initm[i][j] == 0) continue;for(int k = 0; k <= n; ++k){ mm[i][k] += initm[i][j] * dd[j][k];}} } for(int i = 0; i <= n; ++i){ for(int j = 0; j <= n; ++j){ initm[i][j] = mm[i][j]; } }}}void binary_power(int x){if(x == 1)return;binary_power(x/2);if(x % 2)mult2(1);elsemult2(0);}int main(){//freopen("1.txt","r",stdin);while(scanf("%d%d%d",&n,&m,&k)){ if(n + m + k == 0) break; init(); char ch; int x,y; while(k--){ cin >> ch; if(ch == 'g'){ scanf("%d",&x); add(x); mult(initm,addm); } else if(ch == 'e'){ scanf("%d",&x); zero(x); mult(initm,zerom); } else{ scanf("%d%d",&x,&y); exch(x,y); mult(initm,exchm); } } for(int i = 0; i <= n; ++i){ for(int j = 0; j <= n; ++j) dd[i][j] = initm[i][j]; } if(m == 0){ for(int i = 0; i < n - 1; ++i) printf("0 "); printf("0\n"); continue; } binary_power(m); for(int i = 0; i < n - 1; ++i){ printf("%lld ",initm[n][i]); } printf("%lld\n",initm[n][n-1]);}return 0;}