题解：P10045 [CCPC 2023 北京市赛] 线段树

· · 题解

题目大意

题目解决

区间加区间积看着就不是很可做，但是有一条特殊的性质：a_i 恒为奇数。

设 a_i=x_i+1，于是 2|x_i。那么 \prod_{i=l}^r a_i=\prod_{i=l}^r (x_i+1)。

由于答案对 2^{20} 取模，将原式展开，每一项都是不超过 19 个 x_i 的乘积。

那么我们可以线段树维护，对区间 [l,r] 维护 s_i，其中 s_i 表示在 [l,r] 中选择 i 个 x 所得乘积之和，即 \sum_{|S|=i}\prod_{p\in S}x_p。

你在左儿子里边取 j 个数相乘，右儿子里边取 i-j 个数相乘，她们的乘积就等价于在整个区间内选 i 个数相乘。

考虑你有 k 个数并已知她们的 f 值，对所有数加上 v 之后 f 的变化。

考虑 f_{i} 的变化。考虑展开式

(x_1+v)(x_2+v)\dots(x_i+v)-x_1x_2\dots x_i\\=v^i+(x_1+x_2+\dots x_i)v^{i-1}+\dots +(x_1x_2\dots x_{i-1}+x_1x_2\dots x_{i-2}x_i+\dots x_2x_3\dots x_i)v

可以发现，在 x_1 到 x_i 中选 j 个数相乘，将这些乘积求和，会为 f_i' 带来 C_{k-j}^{i-j} \times v^{i-j} 的贡献，所以

f_i'=\sum f_j\times C_{k-j}^{i-j} \times v^{i-j}

组合数是因为，你可以在未选择的 k-j 个数中，再任选 i-j 个数不计算乘积。

这么做时间复杂度是 O(n \log n a^2)，其中 a=20，卡常之后可以通过。

一些卡常技巧：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+3;
int n,q;
#define gc getchar
inline int read(){
    int x=0;
    char c=gc();
    while(c<48) c=gc();
    while(c>47) x=(x<<1)+(x<<3)+(c^48),c=gc();
    return x; 
}
unsigned a[maxn],c[maxn][21],pw[(1<<20)+5][20];
namespace Segtree{
    #define ls (pos<<1)
    #define rs (pos<<1|1)
    unsigned g[20];
    struct Seg{
        int l,r;
        unsigned f[20],add; 
        inline void upd(unsigned x){
            add+=x; x&=1048575;
            for(int i=0;i<20;i++){
                g[i]=0;
                for(int j=0;j<=min(i,r-l+1);j++)
                    g[i]+=c[r-l+1-j][i-j]*f[j]*pw[x][i-j];
            }
            for(int i=0;i<20;i++) f[i]=g[i];
        }
    }tr[maxn<<2];
    #define mid ((tr[pos].l+tr[pos].r)>>1)
    inline void push_u(int pos){
        for(int i=0;i<20;i++){
            tr[pos].f[i]=0;
            for(int j=0;j<=i;j++){
                tr[pos].f[i]+=tr[ls].f[j]*tr[rs].f[i-j];
            }
        }
    }
    inline void push_d(int pos){
        if(tr[pos].add){ 
            tr[ls].upd(tr[pos].add);
            tr[rs].upd(tr[pos].add);
            tr[pos].add=0;
        }
    }
    void build(int pos,int l,int r){
        tr[pos].l=l,tr[pos].r=r;
        if(l==r){
            tr[pos].f[0]=1,tr[pos].f[1]=a[l];
            return;
        }
        build(ls,l,mid);
        build(rs,mid+1,r);
        push_u(pos);
    }
    void up_add(int pos,int l,int r,unsigned x){
        if(l<=tr[pos].l&&tr[pos].r<=r){
            tr[pos].upd(x);
            return;
        }
        push_d(pos);
        if(l<=mid) up_add(ls,l,r,x);
        if(mid<r) up_add(rs,l,r,x);
        push_u(pos);
    }
    unsigned qry(int pos,int l,int r){
        if(l<=tr[pos].l&&tr[pos].r<=r){
            unsigned cur=0;
            for(int i=0;i<20;i++)
                cur+=tr[pos].f[i];
            return cur;
        }
        unsigned cur=1;
        push_d(pos);
        if(l<=mid) cur*=qry(ls,l,r);
        if(mid<r) cur*=qry(rs,l,r);
        return cur;
    }
}using namespace Segtree;
int main(){
//  freopen("a.in","r",stdin);
//  freopen("a.out","w",stdout);
    double T=clock();
    n=read(),q=read();
    for(int i=1;i<=n;i++)
        a[i]=read()-1;
    c[0][0]=1;
    for(int i=1;i<=n;i++){
        c[i][0]=1;
        for(int j=1;j<=min(i,20);j++)
            c[i][j]=c[i-1][j]+c[i-1][j-1];
    }
    for(unsigned i=0;i<(1<<20);i++){
        pw[i][0]=1;
        for(int j=1;j<20;j++)
            pw[i][j]=pw[i][j-1]*i;
    }
    build(1,1,n);
    int op,l,r;
    unsigned x;
    for(int i=1;i<=q;i++){
        op=read(),l=read(),r=read();
        if(op==1){
            x=read();
            up_add(1,l,r,x);
        }
        else printf("%u\n",qry(1,l,r)&1048575);
    }
//  cerr<<clock()-T<<" ms\n";
    return 0;
}

如果有错误与不合理之处，欢迎大家批评指正。