POJ-3735 线性变换构造矩阵

可以根据题目中所给的每轮操作来构造矩阵.. 自己构造的....结果WA了好几次..后来才发现当是s i j 时,应该将i列和j列整个交换...我自己开始时只交换了s[ i ] [ j ] 与 s [ j ] [ i ] ...囧..为了能做出加法运算..构造出的A矩阵是n+1维的..并且初始值矩阵也是n+1列的={0,0,0,...1} ..关于几种操作构造矩阵的方法.程序里体现得很清楚了..

Program:

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<map>
#define ll long long
using namespace std;
struct node
{
      ll s[110][110];   
}h,temp,T,_2M[32];
int n,m,k;
char c;
void Output_Matrix(node a,int n)
{
      int i,j;
      for (i=1;i<=n;i++)
      {
             for (j=1;j<=n;j++) printf("%d ",h.s[i][j]);
             printf("\n");
      }
      printf("-------------------\n");
      return;
}
node Matrix_Mul(node a,node b,int n)
{
      int i,j,k;
      memset(temp.s,0,sizeof(temp.s));
      for (k=1;k<=n;k++)
        for (i=1;i<=n;i++)
          if (a.s[i][k])
            for (j=1;j<=n;j++)
              temp.s[i][j]+=a.s[i][k]*b.s[k][j];
      return temp;
}
node getmatrix(node h,int n,int l)
{
      int i,k,p;
      _2M[0]=h;
      k=1;
      for (p=1;p<=30;p++)
      {
            _2M[p]=Matrix_Mul(_2M[p-1],_2M[p-1],n);
            k*=2;
            if (k>l) break;
      }
      memset(T.s,0,sizeof(T.s));
      for (i=1;i<=n;i++) T.s[i][i]=1;
      while (l)
      {
            while (k>l)
            {
                  k/=2;
                  p--;
            }
            T=Matrix_Mul(T,_2M[p],n);
            l-=k;
      }
      return T;
}
int main()
{
      int i,x,y,p,z;
      while (~scanf("%d%d%d",&n,&m,&k))
      {
             if (!n && !m && !k) break;
             memset(h.s,0,sizeof(h.s));
             for (i=1;i<=n+1;i++) h.s[i][i]=1;
             for (i=1;i<=k;i++)
             {
                   do
                   {
                        c=getchar();
                   }while (c<'a' || c>'z');
                   if (c=='g')
                   {
                         scanf("%d",&x);
                         h.s[n+1][x]++;
                   }else
                   if (c=='e')
                   {
                         scanf("%d",&x);
                         for (y=1;y<=n+1;y++) h.s[y][x]=0; 
                   }else
                   if (c=='s')
                   {
                         scanf("%d%d",&x,&y);
                         if (x==y) continue;
                         for (z=1;z<=n+1;z++)
                         {
                                p=h.s[z][x];
                                h.s[z][x]=h.s[z][y];
                                h.s[z][y]=p;
                         }
                   }
             } 
          //   Output_Matrix(h,n+1);
             h=getmatrix(h,n+1,m);
             node a;
             memset(a.s,0,sizeof(a.s));
             a.s[1][n+1]=1;
             h=Matrix_Mul(a,h,n+1);
         //    Output_Matrix(h,n+1);
             printf("%I64d",h.s[1][1]);
             for (i=2;i<=n;i++) printf(" %I64d",h.s[1][i]);
             printf("\n");            
      }
      return 0;
}