矩阵建模+快速幂

算法核心：矩阵建模，矩阵的快速幂

大意：已知有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
g1
g2
g2
s12
g3
e2

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

初始化下matrix为单位矩阵
1000
0100
0010
0001

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

g2
1000
0100
0010
1101

g2
1000
0100
0010
1201

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

g3
0100
1000
0010
2111

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

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

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

P.S:

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

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

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

 

 

 

CODE:

/*矩阵乘法*/
/*AC代码：172ms*/
#include <iostream>
#define MAXN 105
struct mat
{
    __int64 v[MAXN][MAXN];
    mat()
    {memset(v,0,sizeof(v));}
};
mat e,ans;//e为转换矩阵，ans为e^M
int N,M,K;
mat matrix_mul(mat p1,mat p2)//矩阵乘法
{
    mat t;
    int i,j,k;
    for(i=0;i<=N;i++)
        for(j=0;j<=N;j++)
            if(p1.v[i][j])//优化,不然会TLE
                for(k=0;k<=N;k++)
                    t.v[i][k]+=(p1.v[i][j]*p2.v[j][k]);
                return t;
}
mat matrix_mi(mat p,int k)//矩阵快速幂
{
    mat t;
    for(int i=0;i<=N;i++) t.v[i][i]=1;
    while(k)
    {
        if(k&1)
            t=matrix_mul(t,p);
        k>>=1;
        p=matrix_mul(p,p);
    }
    return t;
}
void Init()
{
    int i,x,y,t;
    char w[2];
    memset(e.v,0,sizeof(e.v));
    for(i=0;i<=N;i++)//初始化e为单位矩阵
        e.v[i][i]=1;
    while(K--)
    {
        scanf("%s",w);
        if(w[0]=='g')//给一个
        {
            scanf("%d",&x);
            x--;//注意
            e.v[N][x]++;
        }
        else if(w[0]=='s')
        {
            scanf("%d%d",&x,&y);
            x--;y--;
            if(x!=y)
            {
                for(i=0;i<=N;i++)
                {t=e.v[i][x];e.v[i][x]=e.v[i][y];e.v[i][y]=t;}
            }
        }
        else
        {
            scanf("%d",&x);
            x--;
            for(i=0;i<=N;i++)
                e.v[i][x]=0;
        }
    }
}
int main()
{
    int i,j;
    while(scanf("%d%d%d",&N,&M,&K)!=EOF)
    {
        if(N==0&&M==0&&K==0) break;
        Init();
        /*
        for(i=0;i<=N;i++)
        {
        for(j=0;j<=N;j++)
        printf("%d ",e.v[i][j]);
        printf("\n");
        }
        */
        ans=matrix_mi(e,M);
        int i;
        for(i=0;i<N;i++)//输出前N个即可
            printf("%I64d ",ans.v[N][i]);
        printf("\n");
    }
    return 0;
}