矩阵快速幂 poj3070 3233 3735 3150 (四)

#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(int k=0;k {
if(a[0][k])
for(int j=0;j {
c[0][j]+=a[0][k]*b[k][j];
if(c[0][j]>=m){c[0][j]%=m;}
}
}
for(int i=1;i {
for(int j=0;j {
c[i][j]=c[i-1][(j-1+n)%n];
}
}
for(int i=0;i {
for(int j=0;j {
b[i][j]=c[i][j];
}
}
}

void expo(LL a[][maxn],int k)
{
if(k==1){
for(int i=0;i {
for(int j=0;j {
e[i][j]=a[i][j];
}
}
return;
}
memset(e,0,sizeof(e));
for(int i=0;i while(k)
{
if(k&1){mul(a,e);}
mul(a,a);
k>>=1;
}
}
int main()
{
LL dat[maxn];
scanf("%d%d%d%d",&n,&m,&d,&k);
for(int i=0;i {
scanf("%lld",&dat[i]);
tmp[0][i]=0;
}
tmp[0][0]=1;
for(int i=1;i<=d;++i)
{
tmp[0][i]=tmp[0][n-i]=1;
}
for(int i=1;i {
for(int j=0;j {
tmp[i][j]=tmp[i-1][(j-1+n)%n];
}
}
expo(tmp,k);
LL ans[maxn];
memset(ans,0,sizeof(ans));
for(int i=0;i {
for(int j=0;j {
ans[i]+=e[i][j]*dat[j];
if(ans[i]>=m){ans[i]%=m;}
}
}
printf("%lld",ans[0]);
for(int i=1;i {
printf(" %lld",ans[i]);
}
printf("\n");
return 0;
}

对于这道题，网上还有一段神代码，在这里同样学习一下

[cpp]
#include
#include
#include
#define LL long long
using namespace std;
int n,m,d,k;
void mul(LL a[],LL b[])
{
int i,j;
LL c[501];
for(i=0;i=j (i-j):(n+i-j)];
for(i=0;i }
LL init[501],tmp[501];
int main()
{
int i,j;
scanf("%d%d%d%d",&n,&m,&d,&k);
for(i=0;i for(tmp[0]=i=1;i<=d;++i)tmp[i]=tmp[n-i]=1;
while(k)
{
if(k&1)mul(tmp,init);
mul(tmp,tmp);
k>>=1;
}
for(i=0;i printf("\n");
return 0;
}