poj-3735-Training little cats-矩阵快速幂

题目链接

题意：有n只小猫咪，你有三种操作,g x:给x小猫咪一个花生, s x y：交换x与y小猫咪的花生，e x：把x小猫咪的花生吃完。现在给你k个操作，问你执行m次这k个操作之后，n个小猫咪各剩多少花生

思路：弱校联盟最后一天的题目。这题m巨大，硬模拟肯定爆炸。当时一神一看题就说这三个操作可以对应矩阵的初等变换（orz，膜一发）。但是如果硬用初等矩阵乘法来做，肯定会超时，每次修改的量其实都很小，直接修改矩阵就行。现构造一个（n+1）的单位方阵，用最后一列来代表每只小猫咪的花生，g操作就直接在a[x][n+1]上+1，s对调x行和y行，e将x行全部清零（注意，这里是将整行都清零，因为这个矩阵的最后一列是描述花生数的向量，实际上最终结果是由前面的n方的矩阵乘上最后一列这个向量得到的，如果只将a[x][n+1]清零，那么在有交换且m>1的情况下就会产生错误，大家可以自己举几个例子试一试），将k个操作整合成一个矩阵，快速幂就能得到最终结果。
一开始这样交是tle，普通的n^3的矩阵乘会超时……考虑到这个矩阵最多只有不超过2n个元素，大部分都是零，所以在乘的时候可以先判断0，将矩阵乘降到n^2……（orz，新姿势）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
long long maxn=102;
struct Matrix
{
    long long mat[103][103];
};
Matrix mul(Matrix a,Matrix b)
{   
    Matrix ret;
    memset(ret.mat,0,sizeof(ret.mat));
	for(int i=0;i<maxn;i++)
        for(int k=0;k<maxn;k++)
        {
            if(a.mat[i][k]!=0)
			for(int j=0;j<maxn;j++)
            {
                ret.mat[i][j]+=a.mat[i][k]*b.mat[k][j];
                //ret.mat[i][j]%=(MOD-1);
            }
        }
    return ret;
}
Matrix pow_M(Matrix a,long long n)
{
    Matrix ret;
    memset(ret.mat,0,sizeof(ret.mat));
    for(int i=0;i<maxn;i++)ret.mat[i][i]=1;
    Matrix temp=a;
    while(n)
    {
        if(n&1)ret=mul(ret,temp);
        temp=mul(temp,temp);
        n>>=1;
    }
    return ret;
}
int main()
{
	long long m;
   int n,k;
   Matrix a;
   
   while(~scanf("%d%lld%d",&n,&m,&k))
   {
    memset(a.mat,0,sizeof(a.mat));
    for(int i=0;i<maxn;i++)
      a.mat[i][i]=1;
   	 if(n==0 && m==0 && k==0)break;
   	 while(k--)
   	 {
   	    char s[5];
	    scanf("%s",&s);
 		if(s[0]=='g')
 		{ int x;
 		  scanf("%d",&x);	
		  a.mat[x][n+1]++;  
		}
		if(s[0]=='s')
		{
			int x,y;
			scanf("%d%d",&x,&y);
			for(int i=0;i<=n+1;i++)
			 swap(a.mat[x][i],a.mat[y][i]);
		}
		if(s[0]=='e')
		{
			int x;
			scanf("%d",&x);
			for(int i=0;i<=n+1;i++)a.mat[x][i]=0; 
		}
	  }
	  Matrix b;
	  b=pow_M(a,m);
	  for(int i=1;i<n;i++)printf("%lld ",b.mat[i][n+1]);
	  printf("%lld\n",b.mat[n][n+1]);
   }
   return 0;
}