首页 > 代码库 > poj3735，，矩阵快速幂
poj3735，，矩阵快速幂
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 9815 | Accepted: 2346 |
Description
Facer‘s pet cat just gave birth to a brood of little cats. Having considered the health of those lovely cats, Facer decides to make the cats to do some exercises. Facer has well designed a set of moves for his cats. He is now asking you to supervise the cats to do his exercises. Facer‘s great exercise for cats contains three different moves:
g i : Let the ith cat take a peanut.
e i : Let the ith cat eat all peanuts it have.
s i j : Let the ith cat and jth cat exchange their peanuts.
All the cats perform a sequence of these moves and must repeat it m times! Poor cats! Only Facer can come up with such embarrassing idea.
You have to determine the final number of peanuts each cat have, and directly give them the exact quantity in order to save them.
Input
The input file consists of multiple test cases, ending with three zeroes "0 0 0". For each test case, three integers n, m and k are given firstly, where n is the number of cats and k is the length of the move sequence. The following k lines describe the sequence.
(m≤1,000,000,000, n≤100, k≤100)
Output
For each test case, output n numbers in a single line, representing the numbers of peanuts the cats have.
Sample Input
3 1 6 g 1 g 2 g 2 s 1 2 g 3 e 2 0 0 0
Sample Output
2 0 1
Source
这题题意如下，有n 只猫咪，三种关于花生的命令 ( 得花生，吃花生，交换花生 ) ，给出一套命令，重复 n 次，问最后每只猫咪得到多少花生。
M那么大，毫无疑问，矩阵快速幂。
先构造一个单位矩阵，因为只需在单位矩阵上进行操作，然后用操作完之后得到的矩阵乘以初始的状态就得到最终的状态。
看下图：
第 i 只猫咪得花生就是在矩阵的第 i 行的最后一列加上1；
注意：如果是 n 只猫咪的话，要用n+1维的矩阵，即n+1维的方阵，多出来的一个才能起到操作的作用！
下面是重点，就是矩阵的快速幂，思路和整数的快速幂一样，不过该过程中会用稀疏矩阵出现，故可借此优化，
即跳过0元素；
我认为要注意的是：矩阵相乘时，需要借助另一个零矩阵，乘完之后再把结果放到该放的矩阵上，而不是直接把结果放到最终的矩阵上！
代码如下：
#include <stdio.h>
#include <string.h>
#include <math.h>
typedef __int64 int64;
int64 c[120][120],ans[120][120],d[120][120];
struct cat
{
int64 p[120][120];
cat(){memset(p,0,sizeof(p));}
};
int main()
{
int64 i,j,m,n,k,x,y,t;
char w[2];
while(scanf("%I64d%I64d%I64d",&n,&m,&k)!=EOF ) //不能用while(scanf(----)!=EOF && n!=0 && m!=0 && k!=0) 这样其中一个为0就退出了
{
if(n==0 && m==0 && k==0)
break;
memset(ans,0,sizeof(ans));
cat ca;
for(i=0;i<=n;i++)
{
ca.p[i][i]=1;
ans[i][i]=1;
}
for(i=0;i<k;i++)
{
scanf("%s",w);
if(w[0]=='g')
{
scanf("%I64d",&x);
ca.p[n][x-1]++;
}
else if(w[0]=='e')
{
scanf("%I64d",&x);
for(j=0;j<=n;j++)
ca.p[j][x-1]=0;
}
else
{
scanf("%I64d%I64d",&x,&y);
for(j=0;j<=n;j++)
{
t=ca.p[j][x-1];
ca.p[j][x-1]=ca.p[j][y-1];
ca.p[j][y-1]=t;
}
}
}
while(m!=0)
{
if(m%2==1)
{
memset(d,0,sizeof(d)); //这里借助了零矩阵d；
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
if(ca.p[i][j])
for(k=0;k<=n;k++)
d[i][k]+=ans[i][j]*ca.p[j][k]; //这里注意一下i，j，k的下标，别弄错了，体会一下
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
ans[i][j]=d[i][j]; //再讲结果即矩阵d放到矩阵ans上，而不是直接把结果放到矩阵ans上
}
memset(c,0,sizeof(c));
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
{
if(ca.p[i][j]==0)
continue;
for(k=0;k<=n;k++)
c[i][k]+=ca.p[i][j]*ca.p[j][k];
}
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
ca.p[i][j]=c[i][j];
m=m/2;
}
for(i=0;i<n-1;i++)
printf("%I64d ",ans[n][i]);
printf("%I64d\n",ans[n][n-1]);
}
return 0;
}