题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1773
本题解用来记录题型，题解来自（侵删）：https://blog.csdn.net/zzkksunboy/article/details/79147935
题意：
有个点，每次点会使的点增加个货物，其中表示在二进制下1的个数，表示点上一次的货物数量。
问时刻之后，每个点货物的数量。
解析：
令时刻的状态为，那么根据题意得出：
怎么看都疑似异或卷积啊，转化一下：
这明显就是异或卷积的形式了，构造向量满足：
那么，快速幂一下就行了。
代码：
#include<bits/stdc++.h> using namespace std; const int MAXN = 2330010; const int MOD = 1e9 + 7; const int inv2 = 5e8 + 4; //2的逆元 int n,N,t,a[MAXN],b[MAXN]; void FWT_xor(int *a,int opt) { for(int i=1;i<N;i<<=1) for(int p=i<<1,j=0;j<N;j+=p) for(int k=0;k<i;++k) { int X=a[j+k],Y=a[i+j+k]; a[j+k]=(X+Y)%MOD;a[i+j+k]=(X+MOD-Y)%MOD; if(opt==-1)a[j+k]=1ll*a[j+k]*inv2%MOD,a[i+j+k]=1ll*a[i+j+k]*inv2%MOD; } } int inline read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int pow_mod(int n,int k) { int res=1; n=n%MOD; while(k>0) { if(k&1) res=(long long)res*n%MOD; n=(long long)n*n%MOD; k>>=1; } return res; } inline void write(int x) { if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); } int main() { n=read(), t=read(); N = 1 << n; for (int i = 0; i < N; i++) { a[i]=read(); } b[0] = 1; for (int i = 0; i < n; i++) { b[1 << i] = 1; } FWT_xor(a, 1); FWT_xor(b, 1); for (int i = 0; i < N; i++) { a[i] = (long long)a[i] * pow_mod(b[i], t) % MOD; } FWT_xor(a, -1); for (int i = 0; i < N; i++) { write((a[i] + MOD) % MOD); putchar(' '); } putchar(10); return 0; }
