}
}
}
}
return ret;
}
met expo(met a,LL k)
{
if(k==1) return a;
met e;
memset(e.at,0,sizeof(e.at));
for(int i=0;i<=n;++i){e.at[i][i]=1;}
if(k==0)return e;
while(k)
{
if(k&1)e=mul(e,a);
k>>=1;
a=mul(a,a);
}
return e;
}
int main()
{
while(~scanf("%lld%lld%lld",&n,&m,&k))
{
LL a,b;
char ch[5];
if(!n&&!k&&!m)break;
memset(d.at,0,sizeof(d.at));
for(int i=0;i<=n;++i)
{d.at[i][i]=1;}
while(k--)
{
scanf("%s",ch);
if(ch[0]=='g')
{
scanf("%lld",&a);
d.at[0][a]++;
}
else if(ch[0]=='e')
{
scanf("%lld",&a);
for(int i=0;i<=n;++i)
{
d.at[i][a]=0;
}
}
else {
scanf("%lld%lld",&a,&b);
for(int i=0;i<=n;++i)
{
LL t=d.at[i][a];
d.at[i][a]=d.at[i][b];
d.at[i][b]=t;
}
}
}
met ans=expo(d,m);
printf("%lld",ans.at[0][1]);
for(int i=2;i<=n;++i)
{
printf(" %lld",ans.at[0][i]);
}
printf("\n");
}
return 0;
}
#include
#include
#include
#define LL long long
using namespace std;
struct met{
LL at[105][105];
};
met ret,d;
LL n,m,k;
met mul(met a,met b)
{
memset(ret.at,0,sizeof(ret.at));
for(int i=0;i<=n;++i)
{
for(int k=0;k<=n;++k)
{
if(a.at[i][k])
{
for(int j=0;j<=n;++j)
{
ret.at[i][j]+=a.at[i][k]*b.at[k][j];
}
}
}
}
return ret;
}
met expo(met a,LL k)
{
if(k==1) return a;
met e;
memset(e.at,0,sizeof(e.at));
for(int i=0;i<=n;++i){e.at[i][i]=1;}
if(k==0)return e;
while(k)
{
if(k&1)e=mul(e,a);
k>>=1;
a=mul(a,a);
}
return e;
}
int main()
{
while(~scanf("%lld%lld%lld",&n,&m,&k))
{
LL a,b;
char ch[5];
if(!n&&!k&&!m)break;
memset(d.at,0,sizeof(d.at));
for(int i=0;i<=n;++i)
{d.at[i][i]=1;}
while(k--)
{
scanf("%s",ch);
if(ch[0]=='g')
{
scanf("%lld",&a);
d.at[0][a]++;
}
else if(ch[0]=='e')
{
scanf("%lld",&a);
for(int i=0;i<=n;++i)
{
d.at[i][a]=0;
}
}
else {
scanf("%lld%lld",&a,&b);
for(int i=0;i<=n;++i)
{
LL t=d.at[i][a];
d.at[i][a]=d.at[i][b];
d.at[i][b]=t;
}
}
}
met ans=expo(d,m);
printf("%lld",ans.at[0][1]);
for(int i=2;i<=n;++i)
{
printf(" %lld",ans.at[0][i]);
}
printf("\n");
}
return 0;
}
4、poj3150题目大意：给定n（1<=n<=500）个数字和一个数字m，这n个数字组成一个环(a0,a1.....an-1)。如果对ai进行一次d-step操作，那么ai的值变为与ai的距离小于d的所有数字之和模m。求对此环进行K次d-step（K<=10000000）后这个环的数字会变为多少。
分析：首先我们要构造矩阵，我们会得到一个500*500的矩阵，那么代码的复杂度就会变成O(log(k)*n^3)，很明显这么高的复杂度会超时的。但是我们发现这个矩阵是一个循环矩阵， 第i行都是第i-1行，右移一位得到的，即a[i][j]=a[i-1][j-1]。很容易我们就可以发现循环矩阵a和循环矩阵b的乘积矩阵c，c[i][j]=sum(a[i][k]*b[k][j])=sum(a[i-1][k-1]*b[j-1][k-1])=c[i-1][j-1]。那么矩阵c也是一个循环矩阵，在做矩阵乘法的时候我们只需要算出第一行的值，其余行直接右移就可以得到，那么算法的复杂度就会变为O(log(k)*n^2)。还需注意的是对于数据范围会超int，要用long long，还有由于矩阵太大了，在函数中申请不了那么大得空间，所以采用指针的方法去写函数。
[cpp]
#include
#include
#include
#define LL long long
using namespace std;
const int maxn=502;
int n,m,d,k;
LL tmp[maxn][maxn],e[maxn][maxn],c[maxn][maxn];
void mul(LL a[][maxn],LL b[][maxn])
{
memset(c,0,sizeof(c));
for