[51nod 1773] A国的贸易

51nod 1773

思路

首先,将$t$次交易按每一次独立地考虑,设$f_i$为交易前国家$i$的货物量,设$g_i$为交易后国家$i$的货物量,$S$为所有二进制表示下数字1的个数为$1$的数集,则可列式得$$g_i=f_i+\sum \limits_{i\oplus j\in S}f_j$$我们稍微改变一下$S$的定义,让$S$中再加一个$0$,那么原式可以化为$$g_i=\sum \limits_{i\oplus j\in S}f_j\\=\sum \limits_{s\in S}\sum \limits_{j\oplus s=i}f_j$$很显然,这个式子可以化为一个异或卷积形式。设$h_i=0/1$表示$i\in S /i\not \in S$,那么原式即为$$g_i=\sum \limits_{j\oplus s=i}f_j\cdot h_s$$

记得暑假在ez听某个人讲过矩阵做这个题,然而已经忘记咋做了2333,当时还百度了一下fwt,找到的是yyb的博客,看得一脸懵逼

还有我求求它了这种明明可以不输出所有方案的题能不能不要强行让大家写个快写啊

代码

#include <iostream>
#include <cstdio>

const int MOD=1e9+7;
int n, t, f[1<<20], g[1<<20], inv2;

void fwt(int *P, int opt){
    for(int i=1; i<(1<<n); i<<=1)
        for(int p=i<<1, j=0; j<(1<<n); j+=p)
            for(int k=0; k<i; k++){
                int X=P[j+k], Y=P[i+j+k];
                P[j+k]=X+Y; P[i+j+k]=X-Y;
                if(P[j+k]>MOD) P[j+k]-=MOD;
                if(P[i+j+k]<0) P[i+j+k]+=MOD;
                if(opt==-1) P[j+k]=1LL*P[j+k]*inv2%MOD, P[i+j+k]=1LL*P[i+j+k]*inv2%MOD;
            }
}

int ksm(int _, int __){
    int ans=1;
    while(__){
        if(__&1) ans=1LL*ans*_%MOD;
        _=1LL*_*_%MOD;
        __>>=1;
    }
    return ans;
}

void input(int &_){
    char ch=getchar(); _=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') _=_*10+ch-'0', ch=getchar();
}

void output(int _){
    int a[13], top=0;
    while(_) a[++top]=_%10, _/=10;
    while(top) putchar('0'+a[top--]);
    putchar(' ');
}

int main(){
    inv2=ksm(2, MOD-2);
    scanf("%d%d", &n, &t); g[0]=1;
    for(int i=0; i<n; i++) g[1<<i]=1;
    for(int i=0; i<(1<<n); i++) input(f[i]);
    fwt(f, 1); fwt(g, 1);
    for(int i=0; i<(1<<n); i++)
        f[i]=1LL*f[i]*ksm(g[i], t)%MOD;
    fwt(f, -1);
    for(int i=0; i<(1<<n); i++) output(f[i]); putchar('\n');
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注