题解 P6673 【[清华集训2016] 石家庄的工人阶级队伍比较坚强】

· · 题解

其实是挺无聊的一个板子题，我不会做真的是败笔。

构造数列 g，若 i 的三进制表示中有 x 个 1 和 y 个 2，则 g_i=b_{x,y}。那么容易发现 f_i 即为 f_{i-1} 与 g 的高维循环卷积，每一维长度为 3（3 进制不进位加法卷积）。

显然我们对它进行三进制的 FWT，即高维 FFT。FFT 的意义是多项式在单位根处的取值，但是我们不方便求三次单位根。

作为一个熟练的选手立即想到扩域。将每个复数表示为 a\omega_3+b 的形式（而非 ai+b），那么根据 \omega_3^3=1 且 \omega_3\ne1，\omega_3^2+\omega_3+1=0 可以定义乘法。

IFWT 的式子可以手解一下三元一次方程。但是我们还需要证明 3 有逆元，这是容易的：若 3\mid p 有 x=y=\dfrac23p 满足 \dfrac1x+\dfrac1y=\dfrac3p。

FWT 是线性变换，所以直接 FWT 过去之后快速幂一下再 IFWT 回来即可。

时间复杂度 O(3^m(m+\log))，轻微卡常。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll readint(){
    ll x=0;
    bool f=0;
    char c=getchar();
    while(!isdigit(c)&&c!='-') c=getchar();
    if(c=='-'){
        f=1;
        c=getchar();
    }
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return f?-x:x;
}
const int maxn=5.4e5,maxm=12+5;
int m,n=1,t,p,b[maxm][maxm],phip;
struct cp{
    int a,b;
    cp operator +(cp x){
        return {(a+x.a)%p,(b+x.b)%p};
    }
    cp operator *(cp x){
        return {(int)((1ll*a*x.b%p+1ll*b*x.a%p-1ll*a*x.a%p+p)%p),(int)((1ll*b*x.b%p-1ll*a*x.a%p+p)%p)};
    }
    cp operator *(ll x){
        return {(int)(1ll*a*x%p),(int)(1ll*b*x%p)};
    }
}f[maxn],g[maxn];
cp ksm(cp a,int b){
    cp ans={0,1};
    while(b){
        if(b%2==1) ans=ans*a;
        a=a*a;
        b/=2;
    }
    return ans;
}
int phi(int n){
    int res=n;
    for(int i=2;i*i<=n;i++) if(n%i==0){
        res=1ll*res*(i-1)/i;
        while(n%i==0) n/=i;
    }
    if(n>1) res=1ll*res*(n-1)/n;
    return res;
}
int ksm(int a,int b){
    int ans=1;
    while(b){
        if(b%2==1) ans=1ll*ans*a%p;
        a=1ll*a*a%p;
        b/=2;
    }
    return ans;
}
void FWT(cp* f,int n,bool flag){
    for(int i=1;i<n;i*=3) for(int j=0;j<n;j+=i*3) for(int k=j;k<j+i;k++){
        cp t0=f[k],t1=f[k+i],t2=f[k+i*2];
        if(flag){
            f[k]=t0+t1+t2;
            f[k+i]=t0+t1*(cp){1,0}+t2*(cp){p-1,p-1};
            f[k+i*2]=t0+t1*(cp){p-1,p-1}+t2*(cp){1,0};
        }
        else{
            f[k]=t0+t1+t2;
            f[k+i]=t0+t1*(cp){p-1,p-1}+t2*(cp){1,0};
            f[k+i*2]=t0+t1*(cp){1,0}+t2*(cp){p-1,p-1};
        }
    }
    if(!flag){
        int invn=ksm(n,phip-1);
        for(int i=0;i<n;i++) f[i]=f[i]*invn;
    }
}
int main(){
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    m=readint();
    for(int i=0;i<m;i++) n*=3;
    t=readint();
    p=readint();
    for(int i=0;i<n;i++) f[i].b=readint();
    for(int i=0;i<=m;i++) for(int j=0;j<=m-i;j++) b[i][j]=readint();
    for(int i=0;i<n;i++){
        int x=i,cnt1=0,cnt2=0;
        for(int j=0;j<m;j++){
            if(x%3==1) cnt1++;
            else if(x%3==2) cnt2++;
            x/=3;
        }
        g[i].b=b[cnt1][cnt2];
    }
    phip=phi(p);
    FWT(f,n,1);
    FWT(g,n,1);
    for(int i=0;i<n;i++) f[i]=f[i]*ksm(g[i],t);
    FWT(f,n,0);
    for(int i=0;i<n;i++) printf("%d\n",f[i].b);
    #ifdef LOCAL
    fprintf(stderr,"%f\n",1.0*clock()/CLOCKS_PER_SEC);
    #endif
    return 0;
}