[51Nod 1773] A国的贸易

题目描述

A国是一个神奇的国家。

这个国家有 2n 个城市，每个城市都有一个独一无二的编号 ，编号范围为0~2n-1。

A国的神奇体现在，他们有着神奇的贸易规则。

当两个城市u，v的编号满足calc（u，v）=1的时候，这两个城市才可以进行贸易（即有一条边相连）。

而calc（u，v）定义为u，v按位异或的结果的二进制表示中数字1的个数。

ex：calc（1,2）=2 ——> 01 xor 10 = 11

calc（100,101）=1 ——> 0110,0100 xor 0110,0101 = 1

calc（233,233）=0 ——> 1110,1001 xor 1110,1001 = 0

每个城市开始时都有不同的货物存储量。

而贸易的规则是：

每过一天，可以交易的城市之间就会交易一次。

在每次交易中，当前城市u中的每个货物都将使所有与当前城市u有贸易关系的城市货物量 +1 。

请问 t 天后，每个城市会有多少货物。

答案可能会很大，所以请对1e9+7取模。

试题分析

多项式乘法一大用处就是利用在快速转移。

只需要像矩阵那样把一维数组的转移关系写出来。

那么对于本题，构造数组B，使得\(B[0]=1,B[2^x]=1\)，其中\(B[0]=1\)是自己还可以保留。

然后进行异或卷积即可。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<vector>

#include<algorithm>

using namespace std;

#define LL long long

inline LL read(){

    LL x=0,f=1; char c=getchar();

    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;

    for(;isdigit(c);c=getchar()) x=x*10+c-'0';

    return x*f;

}

const LL MAXN = (1LL<<22)+11;

const LL INF = 2147483600;

const LL Mod = 1e9+7;

const LL inv2 = 500000004LL;

LL N,T; LL a[MAXN+1],b[MAXN+1];

LL lim;

inline void FWT(LL *A,LL type){

    //for(LL i=0;i<lim;i++) if(rev[i]>i) swap(A[i],A[rev[i]]);

    for(LL mid=1;mid<lim;mid<<=1){

        for(LL R=(mid<<1),j=0;j<lim;j+=R){

            for(LL k=0;k<mid;k++){

                LL x=A[k+j] , y=A[k+j+mid];

                if(type==1) A[k+j]=(x+y)%Mod , A[k+j+mid]=(x-y+Mod)%Mod;

                else A[k+j]=1LL*(x+y)*inv2%Mod , A[k+j+mid]=1LL*(x-y+Mod)%Mod*inv2%Mod;

            }

        }

    }

}

int main(){

    //freopen(".in","r",stdin);

    //freopen(".out","w",stdout);

    N=read(),T=read(); b[0]=1;

    for(LL i=1;i<(1<<N);i<<=1) b[i]=1;

    for(LL i=0;i<(1<<N);i++) a[i]=read();

    lim=(1<<N);N=(1<<N);

    FWT(a,1); FWT(b,1); for(;T;T>>=1){

        for(LL i=0;i<lim;i++){

            if(T&1) a[i]=1LL*a[i]*b[i]%Mod;

            b[i]=1LL*b[i]*b[i]%Mod;

        }

    } FWT(a,-1);

    for(LL i=0;i<N;i++) printf("%lld ",a[i]);

    return 0;

}