solution - P10045

· · 题解

注意到标题为线段树，所以这是一道线段树题。

因为 a_i 都是奇数，又要取模 2^{20}，所以可以把乘积表示成 \prod_i (a_i+1) 的形式，于是将 \prod 展开后，最多不会超过 19 个位置 i 选择将 a_i 放到连乘里（排除掉 a_i = 0 的情况），不然结果一定会是 2^{20} 的倍数。

于是 pushup 解决了，线段树维护一个 f_i 表示选 i 个非 1 的 a_i 连乘的结果之和，暴力背包即可。

同时给个 f_i 的式子：

f_i = \sum _{|S|=i} \prod _{x \in S} a_x

难点在于 pushdown。考虑如何更新 f_i，式子：

f_i' = \sum _{|S|=i} \prod _{x \in S} (a_x + v)

暴力展开，按照 v 的相同次幂合并同类项之后，得到：

f_i' = \sum _{|S|=i} \sum _{j=0} ^i v^{i-j} \left( \sum _{T \subseteq S \land |T|=j} \prod _{x \in T} a_x \right)

即在 S 中选 j 个 a_x 连乘的结果求和再乘上一个 v^{i-j}。

注意到后面那个括号里的和 f_j 的表达式很像，启示我们往 f_j 上凑。

先交换求和顺序：

f_i' = \sum _{j=0} ^i v^{i-j} \left( \sum _{|S|=i} \sum _{T \subseteq S \land |T|=j} \prod _{x \in T} a_x \right)

令当前线段树区间长度为 k。考虑每个 T 会被选多少次，也就是「包含大小为 j 的子集 T 的」大小为 i 的集合个数，显然可以组合数算，考虑固定集合 T，在剩下的 k-j 个元素中选 i-j 个作为 S \setminus T，方案数为 \binom {k-j} {i-j}。

于是得到：

f_i' = \sum _{j=0} ^i v^{i-j} \sum _{|T|=j} \binom {k-j} {i-j} \prod _{x \in T} a_x

把组合数拿出来，后面那一坨就可以替换为 f_j 了，得到：

f_i' = \sum _{j=0} ^i v^{i-j} \binom {k-j} {i-j} f_j

于是就可以直接 pushdown 了。

至于 query，没必要查询区间的时候 merge，直接把每个查询到的线段树节点 u 的 \sum _i f_i 乘起来即可。

复杂度是 O(k^2 (n+q) \log n) 的，其中 k=20，然后还有一个 \frac 1 2 的常数，4s 挺能过的。

然后取模是不需要的，可以用 unsigned 自然溢出实现 {} \bmod 2^{32}，只在查询的时候模个 2^{20} 即可。

代码：

int n,Q,a[N],C[N][20];

class __segt
{
#define mid (l+r>>1)
#define lc v[pos<<1]
#define rc v[pos<<1|1]
#define lcp (pos<<1)
#define rcp (pos<<1|1)

private:
    struct node{int f[20],tg;} v[N<<2];
    int *a,n,lt,rt,k;

    int mx;
    il void pu(int len,int pos)
    {
        mx=min(len,(int)19);
        rep(i,0,mx) v[pos].f[i]=0;
        rep(i,0,mx) rep(j,0,mx-i) v[pos].f[i+j]+=lc.f[i]*rc.f[j];
    }

    int g[20],pw[20];
    il void addtag(int len,int pos,int k)
    {
        v[pos].tg=(v[pos].tg+k),mx=min(len,(int)19);
        pw[0]=1; rep(i,1,mx) pw[i]=pw[i-1]*k;
        rep(i,0,mx)
        {
            g[i]=0;
            rep(j,0,i) g[i]+=pw[i-j]*C[len-j][i-j]*v[pos].f[j];
        }
        rep(i,0,mx) v[pos].f[i]=g[i];
    }

    il void pd(int l,int r,int pos)
    {
        if(!v[pos].tg) return;
        addtag(mid-l+1,lcp,v[pos].tg),addtag(r-mid,rcp,v[pos].tg);
        v[pos].tg=0;
    }

    il void build(int l,int r,int pos)
    {
        if(l==r) return v[pos].f[0]=1,v[pos].f[1]=a[l]-1,void();
        build(l,mid,lcp),build(mid+1,r,rcp);
        pu(r-l+1,pos);
    }

    il void update(int l,int r,int pos)
    {
        if(l>=lt && r<=rt) return addtag(r-l+1,pos,k);
        pd(l,r,pos);
        lt<=mid && (update(l,mid,lcp),1),rt>mid && (update(mid+1,r,rcp),1);
        pu(r-l+1,pos);
    }

    il int query(int l,int r,int pos)
    {
        if(l>=lt && r<=rt)
        {
            mx=min(r-l+1,(int)19);
            int ans=0; rep(i,0,mx) ans+=v[pos].f[i];
            return ans;
        }
        pd(l,r,pos);
        return lt<=mid && rt>mid ? query(l,mid,lcp)*query(mid+1,r,rcp) : lt<=mid ? query(l,mid,lcp) : query(mid+1,r,rcp);
    }

public:
    il void bui(int *_a,int _n){a=_a,n=_n; build(1,n,1);}
    il void upd(int l,int r,int _k){lt=l,rt=r,k=_k; update(1,n,1);}
    il int q(int l,int r){lt=l,rt=r; return query(1,n,1);}

#undef mid
#undef lc
#undef rc
#undef lcp
#undef rcp
} tr;

il void solve()
{
    read(n,Q),_::r(a,n);

    {
        C[0][0]=1;
        rep(i,1,n) rep(j,0,19) C[i][j]=C[i-1][j]+(j?C[i-1][j-1]:0);
    }

    tr.bui(a,n);

    int op,l,r,x;
    while(Q--)
    {
        read(op,l,r);
        if(op==1) read(x),x&&(tr.upd(l,r,x),1);
        else write(tr.q(l,r)&1048575,'\n');
    }
}

华风夏韵，洛水天依！