構築マトリックス+マトリックス高速べき乗POJ 3735

https://vjudge.net/contest/182427#problem/C
この問題の意味は以下の通りで、n匹の猫がいて、3種類の落花生に関する命令(落花生を得る、落花生を食べる、落花生を交換する)があって、1セットの命令を出して、n回繰り返して、最後に猫ごとにどれだけの落花生を得るかを聞きます.Mはそんなに大きくて、間違いなく行列は急速にべき乗します.
まず、単位マトリクス上で操作するだけで、操作が完了した後に得られるマトリクスに初期の状態を乗じて最終的な状態を得るため、単位マトリクスを構築する.次の図を参照してください.
i匹目の猫のピーナッツは行列のi行目の最後の列に1を加えたものです.注意:n匹の猫であれば、n+1次元の行列、すなわちn+1次元の行列を使って、多く出てきた1つが操作の役割を果たすことができます!
次に重点を置くのは、行列の高速べき乗であり、構想は整数の高速べき乗と同じであるが、この過程で疎行列で現れるため、これによって最適化することができ、すなわち0要素をスキップすることができる.
コードは次のとおりです.

#include
#include
#include
#include
#define ll long long
using namespace std;
ll n,m,k;
struct matrix
{
    ll a[120][120];
} init;
matrix multi(matrix x,matrix y)
{
    matrix ans;
    memset(ans.a,0,sizeof(ans.a));
    for(int i=0; i<=n; i++)//          ，         
    {
        for(int k=0; k<=n; k++)
        {
            if(x.a[i][k])
            {
                for(int j=0; j<=n; j++)
                    ans.a[i][j]+=x.a[i][k]*y.a[k][j];
            }
        }
    }
    return ans;
}

matrix mq(ll m)//     
{
    if(m==1)
        return init;
    matrix ans;
    memset(ans.a,0,sizeof(ans.a));//        ，   wrong
    for(int i=0;i<=n;i++)
            ans.a[i][i]=1;
    while(m)
    {
        if(m&1)ans=multi(ans,init);
        m>>=1;
        init=multi(init,init);
    }
    return ans;
}
int main()
{
    char c[10];
    int x,y;
    while(~scanf("%lld%lld%lld",&n,&m,&k),n+m+k)
    {
        memset(init.a,0,sizeof(init.a));
        for(int i=0; i<=n; i++)
            init.a[i][i]=1;
        for(int i=0; iscanf("%s",c);
            if(c[0]=='g')
            {
                scanf("%d",&x);
                init.a[x-1][n]++;
            }
            else if(c[0]=='e')
            {
                scanf("%d",&x);
                for(int j=0; j<=n; j++)
                    init.a[x-1][j]=0;
            }
            else
            {
                scanf("%d %d",&x,&y);
                for(int j=0; j<=n; j++)
                    swap(init.a[x-1][j],init.a[y-1][j]);
            }
        }
        matrix ans=mq(m);
        for(int i=0; i1; i++)
            printf("%lld ",ans.a[i][n]);
        printf("%lld
",ans.a[n-1][n]);
    }
}