|
Training little cats
Description Facer's pet cat just gave birth to a brood of little cats. Having considered the health of those lovely cats, Facer decides to make the cats to do some exercises. Facer has well designed a set of moves for his cats. He is now asking you to supervise the Input The input file consists of multiple test cases, ending with three zeroes "0 0 0". For each test case, three integers n, m and k are given firstly, where n is the number of cats and k is the length of the move Output For each test case, output n numbers in a single line, representing the numbers of peanuts the cats have. Sample Input 3 1 6 g 1 g 2 g 2 s 1 2 g 3 e 2 0 0 0 Sample Output 2 0 1 Source |
题意:有n只猫,k个操作为一个系列,一共做m次
题解:构造矩阵快速幂,先用乘法原理将操作矩阵合并,然后用快速幂,不过普通的会超时,注意到一行最多只有2个不为零的数,所以将乘法改成
for (int i=0;i<N;i++)for (int j=0;j<N;j++)for (int k=0;k<N;k++)
a[i][j]+=b[i][k]*c[k][j];
改写为
for (int i=0;i<N;i++)for (int j=0;j<N;j++)if (b[i][j])for (int k=0;k<N;k++)
a[i][k]+=b[i][j]*c[j][k];
就可以AC了~~~~~
#include<stdio.h>
#include<string.h>
long long n,m,k,c[103],cc[103];
char s[10];
struct point{
long long a[103][103];
}e,res;
struct point mult(struct point x,struct point y)
{
struct point temp;
int i,j,k;
memset(temp.a,0,sizeof(temp.a));
for(i=1;i<=n+1;i++)
{
for(j=1;j<=n+1;j++)
{
if(x.a[i][j])
for(k=1;k<=n+1;k++)
temp.a[i][k]+=x.a[i][j]*y.a[j][k];
}
}
return temp;
};
void gg(int x)
{
int i;
memset(res.a,0,sizeof(res.a));
for(i=1;i<=n+1;i++) res.a[i][i]=1;
res.a[n+1][x]=1;
e=mult(e,res);
}
void ee(int x)
{
int i;
memset(res.a,0,sizeof(res.a));
for(i=1;i<=n+1;i++) res.a[i][i]=1;
res.a[x][x]=0;
e=mult(e,res);
}
void ss(int x,int y)
{
int i;
memset(res.a,0,sizeof(res.a));
for(i=1;i<=n+1;i++) res.a[i][i]=1;
res.a[x][x]=res.a[y][y]=0;
res.a[y][x]=res.a[x][y]=1;
e=mult(e,res);
}
void init()
{
int x,y,i;
memset(c,0,sizeof(c));
memset(e.a,0,sizeof(e.a));
for(i=1;i<=n+1;i++) e.a[i][i]=1;
c[n+1]=1;
for(i=0;i<k;i++)
{
scanf("%s%d",s,&x);
if(s[0]=='g') gg(x);
else if(s[0]=='e') ee(x);
else
{
scanf("%d",&y);
ss(x,y);
}
}
}
void solve()
{
int i;
memset(res.a,0,sizeof(res.a));
for(i=1;i<=n+1;i++) res.a[i][i]=1;
while(m)
{
if(m&1) res=mult(res,e);
e=mult(e,e);
m>>=1;
}
}
void output()
{
int i,j;
for(i=1;i<=n;i++)
{
for(cc[i]=0,j=1;j<=n+1;j++)
{
cc[i]+=c[j]*res.a[j][i];
}
}
for(i=1;i<n;i++) printf("%lld ",cc[i]);
printf("%lld\n",cc[i]);
}
int main()
{
while(scanf("%lld%lld%lld",&n,&m,&k),n||m||k)
{
init();
solve();
output();
}
return 0;
}