更差的阅读体验
逆天 polynomial 做法，做了一整场，糖完了。
首先我们先思考，假设已经知道了序列 \(a\)，要如何求出 \(f(a)_i\)。
那么我们可以按位考虑。假设我们考虑第 \(k\) 位，第 \(k\) 位共有 \(b_k\) 个 \(1\)。那么方案数显然是 \(b_k \choose i\)，然后带 \(2^k\) 的系数。
所以
\[f(a)_i = \sum_{k} {b_k \choose i} \cdot 2^k
\]
很显然推出 \(b\) 后根据每一位 \(1\) 的数量，按位构造就做完了。我们希望用 \(f\) 来反推 \(b\)，然而这不是一个容易反演的形式。
假设 \(f_i = f(a)_i\)。我们可以把二进制位按照 \(b\) 的取值分组。接下来考虑 \(g_i\) 是所有满足 \(b_k = i\) 的 \(2^k\) 之和。那么上面的式子可以改写成
\[f_i = \sum_{j = i} ^ n {j \choose i} g_j
\]
施加二项式反演可以变成
\[g_i = \sum_{j = i} ^ n (-1)^{j - i} {j \choose i} f_j
\]
可以 \(O(n^2)\) 计算，但是还不够。
考虑计算第二类斯特林数·行的手法，拆开组合数，变成
\[g_i = \sum_{j = i} ^ n (-1)^{j - i} \frac{j!}{i!(i-j)!} \cdot f_j
\]
\[i! \cdot g_i = \sum_{j = i} ^ n \frac{(-1)^{j - i}}{(j - i)!} \cdot j! f_j
\]
考虑构造 \(a_i = i! \cdot f_i\)，\(b_i = \frac{(-1)^i}{i!}\)，那么 \(g\) 可以写成差卷积的形式：
\[g_{i - j} \leftarrow a_i b_j
\]
构造 \(b'_j = b_{n - j}\)。那么可以改写成和卷积：
\[g'_{i + j} \leftarrow a_i b'_j
\]
\[g'_{n + i - j} \leftarrow a_i b_j
\]
这样子 \(g_{i} = g'_{i + n}\)，将 \(g\) 二进制拆分即可得到 \(b\)。
那么这道题就做完了。贺一个任意模数多项式乘法板子，复杂度 \(O(n \log n + n \log V)\)。
#include<bits/stdc++.h>
#define endl '\n'
#define N 1000006
#define MOD 1000000007
using namespace std;
namespace poly
{long double const pi=acos(-1);struct comp{long double r,i;comp(){r=i=0;}comp(long double x,long double y){r=x,i=y;}comp conj(){return comp(r,-i);}friend comp operator +(comp x,comp y){return comp(x.r+y.r,x.i+y.i);}friend comp operator -(comp x,comp y){return comp(x.r-y.r,x.i-y.i);}friend comp operator *(comp x,comp y){return comp(x.r*y.r-x.i*y.i,x.i*y.r+x.r*y.i);}};typedef long long ll;int r[1000005];comp a[1000005],b[1000005],c[1000005],d[1000005];void fft(comp *f,int n,int op){for(int i=1;i<n;i++)r[i]=(r[i>>1]>>1)+((i&1)?(n>>1):0);for(int i=1;i<n;i++)if(i<r[i])swap(f[i],f[r[i]]);for(int len=2;len<=n;len<<=1){int q=len>>1;comp wn=comp(cos(pi/q),op*sin(pi/q));for(int i=0;i<n;i+=len){comp w=comp(1,0);for(int j=i;j<i+q;j++,w=w*wn){comp d=f[j+q]*w;f[j+q]=f[j]-d;f[j]=f[j]+d;}}}}void mtt(int *f,int *g,int *h,int n,int p){for(int i=0;i<=n;i++)r[i]=0,a[i]=b[i]=c[i]=d[i]={0,0};for(int i=0;i<n;i++)a[i].r=(f[i]>>15),a[i].i=(f[i]&32767),c[i].r=(g[i]>>15),c[i].i=(g[i]&32767);fft(a,n,1),fft(c,n,1);for(int i=1;i<n;i++)b[i]=a[n-i].conj();b[0]=a[0].conj();for(int i=1;i<n;i++)d[i]=c[n-i].conj();d[0]=c[0].conj();for(int i=0;i<n;i++){compaa=(a[i]+b[i])*comp(0.5,0),bb=(a[i]-b[i])*comp(0,-0.5),cc=(c[i]+d[i])*comp(0.5,0),dd=(c[i]-d[i])*comp(0,-0.5);a[i]=aa*cc+comp(0,1)*(aa*dd+bb*cc),b[i]=bb*dd;}fft(a,n,-1),fft(b,n,-1);for(int i=0;i<n;i++){intaa=(ll)(a[i].r/n+0.5)%p,bb=(ll)(a[i].i/n+0.5)%p,cc=(ll)(b[i].r/n+0.5)%p;h[i]=((1ll*aa*(1<<30)+1ll*bb*(1<<15)+cc)%p+p)%p;}}
}
int fac[N],ifac[N];
inline int qpow(int x,int y=MOD-2)
{int ret=1;for(;y;y>>=1,x=1ll*x*x%MOD)if(y&1)ret=1ll*ret*x%MOD;return ret;
}
inline int binom(int x,int y) {return x<y?0:1ll*fac[x]*ifac[y]%MOD*ifac[x-y]%MOD;}
int n,f[N],g[N];
int a[N],b[N],c[N],ans[N];
void solve()
{scanf("%d",&n);int lim=1;while(lim<=(n+n))lim<<=1;for(int i=0;i<=lim;i++)a[i]=b[i]=c[i]=0;for(int i=1;i<=n;i++)scanf("%d",&f[i]),ans[i]=0;for(int i=0;i<=n;i++){if(i)a[i]=1ll*fac[i]*f[i]%MOD;b[n-i]=ifac[i]; if(i&1)b[n-i]=MOD-b[n-i];}poly::mtt(a,b,c,lim,1e9+7);for(int i=1;i<=n;i++){int now=1ll*c[i+n]*ifac[i]%MOD;for(int j=0;j<=30;j++)if(now>>j&1)for(int k=1;k<=i;k++)ans[k]|=1<<j;}for(int i=1;i<=n;i++)printf("%d%c",ans[i]," \n"[i==n]);
}
main()
{fac[0]=1;for(int i=1;i<N;i++)fac[i]=1ll*fac[i-1]*i%MOD;ifac[N-1]=qpow(fac[N-1]);for(int i=N-2;~i;i--)ifac[i]=1ll*ifac[i+1]*(i+1)%MOD;int T; scanf("%d",&T);while(T--)solve();return 0;
}