构造矩阵 快速幂求解
构造矩阵a[i]为每个cati所拥有的花生总数 这里多加一维用来求和，具体是怎么求得可以看下面的一组例子 假设有3个cat a[] = {1,0,0,0}
构造单位矩阵来保存操作后的解 为什么要是单位矩阵？因为单位矩阵乘以任何矩阵还是原矩阵 这样在单位矩阵上改变要操作的那列（这里用列来表示i只猫的花生数）就能保留下来不被改变的猫的
花生数
对于g 1
(1,0,0,0)*{1,1,0,0
0,1,0,0
0,0,1,0
0,0,0,1}
这样得出结果(1,1,0,0} 也就是说对于g1 就让mat[0][i]+1就可以了 因为加了k 最后都会变成a[i][i]+a[0][0]*k a[i][i]为前一步的i所拥有的花生数 而a[0][0]始终为1
类似的 对于e 1
就是把第1列清0
s i,j
就把第i,j列互换
这样得出一个k个操作后的矩阵T 求解T^m。
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<vector> 7 #include<cmath> 8 #include<queue> 9 #include<set> 10 using namespace std; 11 #define N 102 12 #define LL long long 13 #define INF 0xfffffff 14 const double eps = 1e-8; 15 const double pi = acos(-1.0); 16 const double inf = ~0u>>2; 17 struct Mat 18 { 19 LL mat[N][N]; 20 }; 21 int n; 22 Mat operator * (Mat a,Mat b) 23 { 24 Mat c; 25 memset(c.mat,0,sizeof(c.mat)); 26 int i,j,k; 27 for(k =0 ; k < n ; k++) 28 { 29 for(i = 0 ; i < n ;i++) 30 { 31 if(a.mat[i][k]==0) continue;//优化 32 for(j = 0 ;j < n ;j++) 33 { 34 if(b.mat[k][j]==0) continue;//优化 35 c.mat[i][j] += a.mat[i][k]*b.mat[k][j]; 36 } 37 } 38 } 39 return c; 40 } 41 Mat operator ^(Mat a,int k) 42 { 43 Mat c; 44 int i,j; 45 for(i =0 ; i < n ;i++) 46 for(j = 0; j < n ;j++) 47 c.mat[i][j] = (i==j); 48 for(; k ;k >>= 1) 49 { 50 if(k&1) c = c*a; 51 a = a*a; 52 } 53 return c; 54 } 55 Mat init() 56 { 57 int i; 58 Mat c; 59 memset(c.mat,0,sizeof(c.mat)); 60 for(i = 0 ; i <= n; i++) 61 c.mat[i][i] = 1; 62 return c; 63 } 64 int main() 65 { 66 int i,j,k,m; 67 char s[2]; 68 while(cin>>n>>m>>k) 69 { 70 if(!n&&!k&&!m) break; 71 Mat t = init(); 72 for(i = 1; i <=k; i++) 73 { 74 int x,y; 75 cin>>s>>x; 76 if(s[0]=='g') 77 t.mat[0][x]++; 78 else if(s[0]=='e') 79 { 80 for(j = 0; j <= n ;j++) 81 t.mat[j][x] = 0; 82 } 83 else 84 { 85 cin>>y; 86 for(j =0 ; j <= n; j++) 87 swap(t.mat[j][x],t.mat[j][y]); 88 } 89 } 90 n++; 91 t = t^m; 92 for(i =1 ;i < n-1; i++) 93 cout<<t.mat[0][i]<<" "; 94 cout<<t.mat[0][n-1]<<endl; 95 } 96 return 0; 97 }