【FWT】51Nod1773[A國的貿易]題解

題目概述

有 2n 2 n 個點，每次 i i 點會使 count(i xor j)=1count(i xor j)=1 的 j j 點增加 aiai 個貨物，其中 count(i) c o u n t ( i ) 表示 i i 在二進制下 11 的個數， ai a i 表示 i i 點上一次的貨物數量。

問時刻 tt 之後，每個點貨物的數量。

解題報告

令時刻 t t 的狀态為 ftft ，那麼根據題意得出：

ft,i=ft−1,i+∑i xor j=2kft−1,j(1) (1) f t , i = f t − 1 , i + ∑ i   x o r   j = 2 k f t − 1 , j

怎麼看都疑似異或卷積啊，轉化一下：

ft,i=ft−1,i+∑j xor 2k=ift−1,j(2) (2) f t , i = f t − 1 , i + ∑ j   x o r   2 k = i f t − 1 , j

這明顯就是異或卷積的形式了，構造向量 A A 滿足：

A0=1,Ai=[∃2k=i](3)(3)A0=1,Ai=[∃2k=i]

那麼 ft=ft−1⊕A f t = f t − 1 ⊕ A ，快速幂一下就行了。

示例程式

#include<cstdio>
#include<cctype>
using namespace std;
typedef long long LL;
const int maxn=<<,MOD=+,INV2=MOD+>>;

int n,m,A[maxn+],num[maxn+];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,,,stdin);
    if (l==r) return EOF;return *l++;
}
inline int readi(int &x){
    int tot=,f=;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    if (lst=='-') f=-f;
    while (isdigit(ch)) tot=(tot<<)+(tot<<)+(ch^),ch=readc();
    return x=tot*f,Eoln(ch);
}
inline void writei(int x){
    static int buf[],len;len=;do buf[len++]=x%,x/=; while (x);
    while (len) putchar(buf[--len]+);
}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline void FWT(int *a,int n,int f){
    for (int k=;k<n;k<<=)
        for (int i=;i<n;i+=k<<)
            for (int j=;j<k;j++){
                int 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<) a[i+j]=(LL)a[i+j]*INV2%MOD,a[i+j+k]=(LL)a[i+j+k]*INV2%MOD;
            }
}
inline int Pow(int w,int b){
    int s=;
    while (b) {if (b&) s=(LL)s*w%MOD;b>>=;if (b) w=(LL)w*w%MOD;}
    return s;
}
int main(){
    readi(n);readi(m);for (int i=;i<(<<n);i++) readi(num[i]);
    A[]=;for (int i=;i<n;i++) A[<<i]=;FWT(A,<<n,);FWT(num,<<n,);
    for (int i=;i<(<<n);i++) num[i]=(LL)num[i]*Pow(A[i],m)%MOD;FWT(num,<<n,-);
    for (int i=;i<(<<n)-;i++) writei(num[i]),putchar(' ');writei(num[(<<n)-]);
    return putchar('\n'),;
}