【NTT】【真·二维卷积】Codechef Chef and Bike
发布时间
阅读量：
阅读量
分析：
太忙（lan）了不想写，附我看的链接
https://www.cnblogs.com/ivorysi/p/8868453.html
#include<cstdio>
#include<cstring>
#include<algorithm>
#define SF scanf
#define PF printf
#define MAXN 25
#define MAXM 10010
#define MOD 1163962801
using namespace std;
typedef long long ll;
ll px[MAXN],py[MAXN],v1[MAXM],v2[MAXM],w[MAXN][MAXN],v[MAXN][MAXN][MAXN][MAXN];
int st[MAXM],ed[MAXM];
const ll G=46;
int N,M;
ll T;
struct Matrix{
ll a[MAXN][MAXN];
Matrix operator * (const Matrix &b) const {
Matrix c;
c.clear();
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
for(int k=0;k<N;k++)
c.a[i][j]=(c.a[i][j]+a[i][k]*b.a[k][j]%MOD)%MOD;
return c;
}
void clear(){
memset(a,0,sizeof a);
}
void Setup(int x,int y){
clear();
for(int i=0;i<M;i++)
a[st[i]][ed[i]]=(a[st[i]][ed[i]]+px[v1[i]*x%N]*py[v2[i]*y%(N-1)]%MOD)%MOD;
}
}I,Ans;
ll fsp(ll x,ll y){
ll res=1;
while(y){
if(y&1ll)
res=res*x%MOD;
x=x*x%MOD;
y>>=1ll;
}
return res;
}
void fspM(ll y){
Ans.clear();
for(int i=0;i<N;i++)
Ans.a[i][i]=1;
while(y){
if(y&1ll)
Ans=Ans*I;
I=I*I;
y>>=1ll;
}
}
void Prepare(){
SF("%d%d%lld",&N,&M,&T);
for(int i=0;i<M;i++){
SF("%d%d%lld%lld",&st[i],&ed[i],&v1[i],&v2[i]);
st[i]--;
ed[i]--;
v1[i]%=N;
v2[i]%=(N-1);
}
px[0]=1;
py[0]=1;
px[1]=fsp(G,(MOD-1)/N);
py[1]=fsp(G,(MOD-1)/(N-1));
for(int i=2;i<=N;i++)
px[i]=px[i-1]*px[1]%MOD;
for(int i=2;i<=N-1;i++)
py[i]=py[i-1]*py[1]%MOD;
}
void DFT1(int x){
for(int i=0;i<N;i++)
for(int j=0;j<N-1;j++){
w[i][j]=0;
for(int k=0;k<N;k++)
for(int l=0;l<N-1;l++)
w[i][j]=(w[i][j]+v[x][x][k][l]*px[N-i*k%N]%MOD*py[N-1-j*l%(N-1)]%MOD)%MOD;
w[i][j]=w[i][j]*fsp(N*(N-1),MOD-2)%MOD;
}
}
int main(){
Prepare();
for(int i=0;i<N;i++)
for(int j=0;j<N-1;j++){
I.Setup(i,j);
fspM(T);
for(int k=0;k<N;k++)
for(int l=0;l<N;l++)
v[k][l][i][j]=Ans.a[k][l];
}
for(int i=0;i<N;i++){
DFT1(i);
for(int j=0;j<N;j++){
for(int k=0;k<N-1;k++)
PF("%lld ",w[j][k]);
PF("\n");
}
}
}
代码解释全部评论 (0)
还没有任何评论哟~