题目概述

$a_{t}[i]=\sum_{j}a_{t-1}[j]b[count(i\ xor\ j)]$ ，其中 $count(i)$ 表示 $i$ 二进制下 $1$ 的个数。给出 $a_0,b$ ，求 $a_t$ 。

解题报告

令 $c[i]=b[count(i)]$ ，那么 $a_{t}=a_{t-1}*c$ （ $*$ 表示异或卷积），FWT裸题？

但是模数可能是偶数？WTF？我们可以先将模数扩大 $n$ 倍，然后就可以在FWT的最后直接除以 $n$（考虑到模其实是减法，所以肯定有 $n​$ 这个因子）。

但是这样会爆long long，所以要快速（慢速）乘。

示例程序

#include<cstdio>
#include<cctype>
using namespace std;
typedef long long LL;typedef long double DB;
const int maxm=20,maxn=1<<20;

int n;LL t,MOD,a[maxn+5],b[maxm+5],c[maxn+5],cnt[maxn+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
inline void AMOD(LL &x,LL tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline LL Mul(LL x,LL y) {return (x*y+MOD-(LL)((DB)x/MOD*y)*MOD)%MOD;}
inline LL Pow(LL w,LL b) {LL s;for (s=1;b;w=Mul(w,w),b>>=1) if (b&1) s=Mul(s,w);return s;}
inline void FWT(LL *a,int n,int f){
    for (int k=1;k<n;k<<=1)
        for (int i=0;i<n;i+=k<<1)
            for (int j=0;j<k;j++)
                {LL x=a[i+j],y=a[i+j+k];AMOD(a[i+j]=x,y),AMOD(a[i+j+k]=x,MOD-y);}
    if (f<0) for (int i=0;i<=n;i++) a[i]/=n;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    readi(n);readi(t);readi(MOD);MOD*=(1<<n);
    for (int i=0;i<(1<<n);i++) readi(a[i]),a[i]%=MOD;for (int i=0;i<=n;i++) readi(b[i]),b[i]%=MOD;
    n=1<<n;for (int i=0;i<n;i++) c[i]=b[cnt[i]=cnt[i>>1]+(i&1)];FWT(a,n,1);FWT(c,n,1);
    for (int i=0;i<n;i++) a[i]=Mul(a[i],Pow(c[i],t));FWT(a,n,-1);
    for (int i=0;i<n;i++) printf("%lld\n",a[i]);return 0;
}