`
wbj0110
  • 浏览: 1536436 次
  • 性别: Icon_minigender_1
  • 来自: 上海
文章分类
社区版块
存档分类
最新评论

矩阵建模+快速幂

阅读更多

算法核心:矩阵建模,矩阵的快速幂


大意:已知有n只猫咪,开始时每只猫咪有花生米0颗,先有一组操作:
由下面三个中的k个操作组成:
g i 给i只猫咪一颗花生米
e i 让第i只猫咪吃掉它拥有的所有花生米
s i j 将猫咪i与猫咪j的拥有的花生米交换

  现将上述操作做m次后,问每只猫咪有多少颗花生米?

 

分析:
因m的数据范围较大,用矩阵连乘。
构建矩阵模型,peanut[N] = {0,0,。。。。0,1}:即前n个数为0,最后一个数取1
matrix[N][N],初始化条件下为单位矩阵,。。。
对猫咪进行操作转化为在对矩阵peanut进行操作,一组操作过程转化为矩阵matrix,那么m次操作,即对peanut*(matrix^m)
EXP:
input:
316

g
1
g
2
g
2
s
12
g
3
e
2

初始化下矩阵:peanut 
0001即每只猫咪的花生米个数为0

初始化下matrix为单位矩阵
1000

0100
0010
0001

经过操作
g
1
给1号1颗花生米,即在第一列的最后一行加1
1000
0100
0010
1001

g
2
1000
0100
0010
1101

g
2
1000
0100
0010
1201

s
12
//即交换第1,2列
0100
1000
0010
2101

g
3
0100
1000
0010
2111

e
2
//将第2列全部置为0
0000
1000
0010
2011

最后peanut
=peanut*matrix*matrix.....*matrix=peanut*(matrix^m)故可用矩阵快速求幂
peanut的前n个数即为每只猫咪拥有的花生米数

-----------------------------------------------------------------------

P.S:

再说下几个要注意的地方:

(1):要注意在矩阵相乘的时候判断一下相乘的两个元素是否为0,否则会超时.

(2):要用__int64,结果超出了int型.

 

 

 

CODE:

  1. /*矩阵乘法*/  
  2. /*AC代码:172ms*/  
  3. #include <iostream>  
  4. #define MAXN 105  
  5. struct mat  
  6. {  
  7.     __int64 v[MAXN][MAXN];  
  8.     mat()  
  9.     {memset(v,0,sizeof(v));}  
  10. };  
  11. mat e,ans;//e为转换矩阵,ans为e^M  
  12. int N,M,K;  
  13. mat matrix_mul(mat p1,mat p2)//矩阵乘法  
  14. {  
  15.     mat t;  
  16.     int i,j,k;  
  17.     for(i=0;i<=N;i++)  
  18.         for(j=0;j<=N;j++)  
  19.             if(p1.v[i][j])//优化,不然会TLE  
  20.                 for(k=0;k<=N;k++)  
  21.                     t.v[i][k]+=(p1.v[i][j]*p2.v[j][k]);  
  22.                 return t;  
  23. }  
  24. mat matrix_mi(mat p,int k)//矩阵快速幂  
  25. {  
  26.     mat t;  
  27.     for(int i=0;i<=N;i++) t.v[i][i]=1;  
  28.     while(k)  
  29.     {  
  30.         if(k&1)  
  31.             t=matrix_mul(t,p);  
  32.         k>>=1;  
  33.         p=matrix_mul(p,p);  
  34.     }  
  35.     return t;  
  36. }  
  37. void Init()  
  38. {  
  39.     int i,x,y,t;  
  40.     char w[2];  
  41.     memset(e.v,0,sizeof(e.v));  
  42.     for(i=0;i<=N;i++)//初始化e为单位矩阵  
  43.         e.v[i][i]=1;  
  44.     while(K--)  
  45.     {  
  46.         scanf("%s",w);  
  47.         if(w[0]=='g')//给一个  
  48.         {  
  49.             scanf("%d",&x);  
  50.             x--;//注意  
  51.             e.v[N][x]++;  
  52.         }  
  53.         else if(w[0]=='s')  
  54.         {  
  55.             scanf("%d%d",&x,&y);  
  56.             x--;y--;  
  57.             if(x!=y)  
  58.             {  
  59.                 for(i=0;i<=N;i++)  
  60.                 {t=e.v[i][x];e.v[i][x]=e.v[i][y];e.v[i][y]=t;}  
  61.             }  
  62.         }  
  63.         else  
  64.         {  
  65.             scanf("%d",&x);  
  66.             x--;  
  67.             for(i=0;i<=N;i++)  
  68.                 e.v[i][x]=0;  
  69.         }  
  70.     }  
  71. }  
  72. int main()  
  73. {  
  74.     int i,j;  
  75.     while(scanf("%d%d%d",&N,&M,&K)!=EOF)  
  76.     {  
  77.         if(N==0&&M==0&&K==0) break;  
  78.         Init();  
  79.         /* 
  80.         for(i=0;i<=N;i++) 
  81.         { 
  82.         for(j=0;j<=N;j++) 
  83.         printf("%d ",e.v[i][j]); 
  84.         printf("\n"); 
  85.         } 
  86.         */  
  87.         ans=matrix_mi(e,M);  
  88.         int i;  
  89.         for(i=0;i<N;i++)//输出前N个即可  
  90.             printf("%I64d ",ans.v[N][i]);  
  91.         printf("\n");    
  92.     }  
  93.     return 0;  
  94. }  
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics