题解：CF2211D AND-array

· · 题解

更好的阅读体验

逆天 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++)
        {
            comp
            aa=(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++)
        {
            int
            aa=(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;
}