首页 > 代码库 > poj3735—Training little cats（特殊操作转化为矩阵操作）
poj3735—Training little cats（特殊操作转化为矩阵操作）
题目链接：http://poj.org/problem?id=3735
题目意思：
调教猫咪：有n只饥渴的猫咪，现有一组羞耻连续操作，由k个操作组成，全部选自：
1. g i 给第i只猫咪一颗花生
2. e i 让第i只猫咪吃光它的花生
3. s i j 交换猫咪i与猫咪j的花生
现将上述一组连续操作做m次后，求每只猫咪有多少颗花生？
思路：这道题难点在如何把这种奇怪的操作转化为矩阵操作，网络上看到一个画的很好的图，这里直接偷过来。
现在，对于每一个操作我们都可以得到一个转置矩阵，把k个操作的矩阵相乘我们可以得到一个新的转置矩阵T。A * T 表示我们经过一组操作，类似我们可以得到经过m组操作的矩阵为 A * T ^ m,最终矩阵的[0][1~n]即为答案。
上述的做法比较直观，但是实现过于麻烦，因为要构造k个不同矩阵。有没有别的方法可以直接构造转置矩阵T？答案是肯定的。
我们还是以单位矩阵为基础：
对于第一种操作g i，我们使Mat[0][i] = Mat[0][i] + 1
对于第二种操作e i，我们使矩阵的第i列清零；
对于第三种操作s i j，我们使第i列与第j列互换。
这样实现的话，我们始终在处理一个矩阵，免去构造k个矩阵的麻烦。
至此，构造转置矩阵T就完成了，接下来只需用矩阵快速幂求出 A * T ^ m即可，还有一个注意的地方，该题需要用到long long。
这里还要说一下T*A=A*T的转置。
代码：
1 //Author: xiaowuga 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #define maxx INT_MAX 6 #define minn INT_MIN 7 #define inf 0x3f3f3f3f 8 #define N 105 9 using namespace std; 10 typedef long long ll; 11 ll n,size;//第n项，矩阵大小 12 struct Matrix{ 13 ll mat[N][N]; 14 void clear(){ 15 memset(mat,0,sizeof(mat)); 16 } 17 Matrix operator * (const Matrix & m) const{ 18 Matrix tmp; 19 int i ,j,k; 20 tmp.clear(); 21 for( i=0;i<size;i++) 22 for( k=0;k<size;k++){ 23 if(mat[i][k]==0) continue; 24 for( j=0;j<size;j++){ 25 tmp.mat[i][j]+=mat[i][k]*m.mat[k][j]; 26 } 27 } 28 return tmp; 29 } 30 }; 31 void POW(Matrix m,ll k){ 32 Matrix ans; 33 memset(ans.mat,0,sizeof(ans.mat)); 34 for(int i=0;i<size;i++) ans.mat[i][i]=1; 35 while(k){ 36 if(k&1) ans=ans*m; 37 k/=2; 38 m=m*m; 39 } 40 for(int i=1;i<size;i++){ 41 cout<<ans.mat[0][i]<<" "; 42 } 43 cout<<endl; 44 } 45 int main() { 46 Matrix m; 47 int k; 48 while(cin>>size>>n>>k&&(size+n+k)){ 49 size++; 50 m.clear(); 51 for(int i=0;i<size;i++) m.mat[i][i]=1; 52 for(int i=0;i<k;i++){ 53 char t[5]; 54 int num1,num2; 55 cin>>t; 56 if(t[0]==‘g‘){ 57 cin>>num1; 58 m.mat[0][num1]++; 59 } 60 else if(t[0]==‘e‘){ 61 cin>>num1; 62 for(int j=0;j<size;j++){ 63 m.mat[j][num1]=0; 64 } 65 } 66 else{ 67 cin>>num1>>num2; 68 for(int j=0;j<size;j++) 69 swap(m.mat[j][num1],m.mat[j][num2]); 70 } 71 } 72 POW(m,n); 73 } 74 return 0; 75 }
poj3735—Training little cats（特殊操作转化为矩阵操作）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。