poj 3735 （矩阵快速幂）

题意：有n只猫咪，开始时每只猫咪有花生0颗，现有一组操作，由下面三个中的k个操作组成：
               1. g i 给i只猫咪一颗花生米
               2. e i 让第i只猫咪吃掉它拥有的所有花生米
               3. s i j 将猫咪i与猫咪j的拥有的花生米交换

现将上述一组操作做m次后，问每只猫咪有多少颗花生？

解题报告：http://www.cnblogs.com/acSzz/archive/2012/08/20/2648087.html

View Code

  1 // File Name: 3735.cpp
  2 // Author: Missa
  3 // Created Time: 2013/2/7 星期四 12:35:55
  4 
  5 #include<iostream>
  6 #include<cstdio>
  7 #include<cstring>
  8 #include<algorithm>
  9 #include<cmath>
 10 #include<queue>
 11 #include<stack>
 12 #include<string>
 13 #include<vector>
 14 #include<cstdlib>
 15 #include<map>
 16 using namespace std;
 17 #define ll long long
 18 ll n,m,k;
 19 //**********矩阵快速幂********************
 20 const int maxn=105;//矩阵最大范围
 21 //int n,m;//矩阵n*m
 22 struct Mat
 23 {
 24     ll mat[maxn][maxn];
 25     void clear()
 26     {
 27         memset(mat,0,sizeof(mat));
 28     }
 29     void unit()//单元矩阵n*n矩阵的时候需要
 30     {
 31         clear();
 32         for(int i=0;i<=n;i++)
 33             mat[i][i]=1;
 34     }
 35 };
 36 Mat a;
 37 void init()
 38 {
 39     a.unit();
 40 }
 41 Mat mul(Mat a,Mat b)
 42 {
 43     Mat c;
 44     c.clear();
 45     for(int i=0;i<=n;i++)//n+1 * n+1 的矩阵
 46     {
 47         for(int k=0;k<=n;k++)
 48         {
 49             if(a.mat[i][k])
 50             {
 51                 for(int j=0;j<=n;j++)
 52                     c.mat[i][j]+=a.mat[i][k]*b.mat[k][j];
 53             }
 54         }
 55     }
 56     return c;
 57 }
 58 Mat mpow(Mat a,ll k)//非递归实现
 59 {
 60     if(k==1) return a;
 61     Mat e;
 62     e.unit();
 63     while(k)
 64     {
 65         if(k&1)     e=mul(e,a);
 66         k>>=1;
 67         a=mul(a,a);
 68     }
 69     return e;
 70 }
 71 //***********矩阵快速幂*******************
 72 
 73 int main()
 74 {
 75     while(~scanf("%lld%lld%lld",&n,&m,&k))
 76     {
 77         if(!n && !m && !k) break;
 78         init();
 79         while(k--)
 80         {
 81             ll x,y;
 82             char o[10];
 83             scanf("%s",&o);
 84             if(o[0]=='g')
 85             {
 86                 scanf("%lld",&x);
 87                 a.mat[0][x]++;
 88             }
 89             else if(o[0]=='e')
 90             {
 91                 scanf("%lld",&x);
 92                 for(int i=0;i<=n;i++)
 93                     a.mat[i][x]=0;
 94             }
 95             else
 96             {
 97                 scanf("%lld%lld",&x,&y);
 98                 for(int i=0;i<=n;i++)
 99                     swap(a.mat[i][x],a.mat[i][y]);
100             }
101         }
102         if(m==0)
103         {
104             printf("0");
105             for(int i=2;i<=n;i++)
106                 printf(" 0");
107             printf("\n");
108             continue;
109         }
110         a=mpow(a,m);
111         printf("%lld",a.mat[0][1]);
112         for(int i=2;i<=n;i++)
113             printf(" %lld",a.mat[0][i]);
114         printf("\n");
115     }
116     return 0;
117 }