可以根据题目中所给的每轮操作来构造矩阵.. 自己构造的....结果WA了好几次..后来才发现当是s i j 时,应该将i列和j列整个交换...我自己开始时只交换了s[ i ] [ j ] 与 s [ j ] [ i ] ...囧..为了
可以根据题目中所给的每轮操作来构造矩阵.. 自己构造的....结果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;
}