poj 3735 大数量反复操作问题（矩阵高速幂）

题意：一个一维数组，3种操作： a:  第i个数+1，b: 第i个数=0 ，c:：交换某俩处的数。  由三种基本操作构成一组序列，反复该序列m次（m<10^9），问结果

属于一种综合操作反复型： 每次乘以一矩阵T，相当于做一次操作。关键是构造这个矩阵。

先构造最初矩阵A :  1*（n +1） ={1，0，0，0…} ，  第一个一时为了操作第一行数的，

T的构造：初始是N+1 * N+1单位阵 这样恰好操作第i个数， +1，就在第0行的第 i个加1；交换就相应列交换，清零就相应列清0.

ans= A*(T^m); 注意用；long long

#include<iostream>
#include<cstring>
using namespace std;
struct juz
{
    long long  bat[105][105];
    int x,y;     //行 列
    juz ()
    {
        memset(bat,0,sizeof(bat));
        x=0;y=0;
    }
};
juz mutp(juz a,juz b)
{
    juz c;
    c.x=a.x;c.y=b.y;
    memset(c.bat,0,sizeof(c.bat));
    for(int k=0;k<a.y;k++)
          for(int i=0;i<a.x;i++)
          if(a.bat[i][k])
          {
              for(int j=0;j<b.y;j++)
              {
                  c.bat[i][j]+=(a.bat[i][k]*b.bat[k][j]);
              }
          }
    return c;
}
juz quickf(juz a,int k)
{
    juz c=a;
    for(int i=0;i<a.x;i++)
      for(int j=0;j<a.x;j++)
          c.bat[i][j]=(i==j);
    while(k>=1)
    {
        if(k%2)
            c=mutp(c,a);
        k=k/2; a=mutp(a,a);
    }
    return c;
}
int main()
{
    int n,m,k;
    while(cin>>n>>m>>k&&(n||m||k))
    {
        juz a,b,c;
        a.x=1;a.y=n+1; b.x=n+1;b.y=n+1;
        for(int i=0;i<=n;i++)
        {
            a.bat[0][i]=0;
            b.bat[i][i]=1;
        }
        a.bat[0][0]=1;
        char tmp;
        int xx,yy;
        for(int i=0;i<k;i++)
        {
            cin>>tmp;
            if(tmp=='g')
            {
                cin>>xx;
                b.bat[0][xx]++;
            }
            else if(tmp=='e')
            {
                cin>>xx;
                for(int i=0;i<=n;i++)
                  b.bat[i][xx]=0;
            }
            else
            {
                cin>>xx>>yy;
                for(int i=0;i<=n;i++)
                {
                    int tx=b.bat[i][xx];
                    b.bat[i][xx]=b.bat[i][yy];
                    b.bat[i][yy]=tx;
                }
            }
        }
        c=quickf(b,m);
        c=mutp(a,c);
       for(int i=1;i<=n;i++)
         if(i!=n)cout<<c.bat[0][i]<<" ";
         else cout<<c.bat[0][i]<<endl;
    }
    return 0;
}