zcmimi's blog
查看原题

点击跳转

可以发现查询的c\le 20,那么我们直接对每个节点记录每个c的答案

区间加

设当前区间a_1,a_2,\dots,a_n

区间加后:a_1+x,a_2+x,\dots,a_n+x

选取i个方案:

\begin{aligned} &\quad (a_1+x)(a_2+x)\cdots(a_i+x)\\ &=a_1a_2\cdots a_i+xa_2a_3\cdots a_i+x^2a_3a_4\cdots a_i+\dots\\ &=a_1a_2\cdots a_i+\sum_{j=1}^ix^j \left( \text{从i个数中取出i-j个数的乘积之和} \right) \end{aligned}

该区间取i个数的乘积之和增加的贡献:

\displaystyle ans_i\operatorname{+=}\sum_{j=0}^i x^{i-j}ans_j{n-j\choose i-j}

区间反转

选取奇数个的答案变成相反数

选取偶数个的答案没有影响

区间查询

设当前答案为ans,左儿子答案为l,右儿子答案为r

\displaystyle ans_i=\sum_{j=0}^i l_j\times r_{i-j}

(左边选j个,右边选i-j个)

#include<bits/stdc++.h>
const int N=50011,P=19940417;
int n,q,C[N][21];
int min(int x,int y){return x<y?x:y;}
void mod(int&x){if(x>=P)x-=P;}
struct node{
    int len,laz,re,a[21];
    node(){memset(a,0,sizeof a);len=laz=re=0;}
    void add(int v){
        static int t[21];t[0]=1;
        for(int i=1;i<=20&&i<=len;++i)t[i]=1ll*t[i-1]*v%P;
        for(int i=min(20,len);i;--i)
            for(int j=0;j<i;++j)
                mod(a[i]+=1ll*a[j]*t[i-j]%P*C[len-j][i-j]%P);
        mod(laz+=v);
    }
    void rev(){
        for(int i=1;i<=20&&i<=len;i+=2)a[i]=P-a[i];
        laz=P-laz;
        re^=1;
    }
}s[N<<2];
#define ls rt<<1
#define rs rt<<1|1
void mg(node&s,const node&l,const node&r){
    for(int i=0;i<=20&&i<=s.len;++i){
        s.a[i]=0;
        for(int j=0;j<=i;++j)
            mod(s.a[i]+=1ll*l.a[j]*r.a[i-j]%P);
    }
}
void pu(int rt){mg(s[rt],s[ls],s[rs]);}
void pd(int rt){
    if(s[rt].re)
        s[ls].rev(),s[rs].rev(),
        s[rt].re=0;
    if(s[rt].laz)
        s[ls].add(s[rt].laz),s[rs].add(s[rt].laz),
        s[rt].laz=0;
}
void build(int l,int r,int rt){
    s[rt].len=r-l+1;
    if(l==r){
        s[rt].a[0]=1;
        int x;
        scanf("%d",&x);
        mod(s[rt].a[1]=x%P+P);
        return;
    }
    int m=l+r>>1;
    build(l,m,ls);build(m+1,r,rs);
    pu(rt);
}
void upd(int L,int R,int v,int l,int r,int rt){
    if(L<=l&&r<=R)return s[rt].add(v),void();
    int m=l+r>>1;
    pd(rt);
    if(L<=m)upd(L,R,v,l,m,ls);
    if(R>m)upd(L,R,v,m+1,r,rs);
    pu(rt);
}
void Rev(int L,int R,int l,int r,int rt){
    if(L<=l&&r<=R)return s[rt].rev(),void();
    int m=l+r>>1;
    pd(rt);
    if(L<=m)Rev(L,R,l,m,ls);
    if(R>m)Rev(L,R,m+1,r,rs);
    pu(rt);
}
node ask(int L,int R,int l,int r,int rt){
    if(L==l&&r==R)return s[rt];
    int m=l+r>>1;
    pd(rt);
    if(L>m)return ask(L,R,m+1,r,rs);
    else if(R<=m)return ask(L,R,l,m,ls);
    else{
        node s,sl=ask(L,m,l,m,ls),sr=ask(m+1,R,m+1,r,rs);
        s.len=sl.len+sr.len;
        mg(s,sl,sr);
        return s;
    }
}
int main(){
    scanf("%d%d",&n,&q);
    C[0][0]=1;
    for(int i=1;i<=n;++i){
        C[i][0]=1;
        for(int j=1;j<=20&&j<=i;++j)
            mod(C[i][j]=C[i-1][j]+C[i-1][j-1]);
    }
    build(1,n,1);
    char opt[5];int l,r,c;
    while(q--){
        scanf("%s%d%d",opt,&l,&r);
        if(opt[0]=='R')
            Rev(l,r,1,n,1);
        else if(opt[0]=='I')
            scanf("%d",&c),
            mod(c=c%P+P),
            upd(l,r,c,1,n,1);
        else
            scanf("%d",&c),
            printf("%d\n",ask(l,r,1,n,1).a[c]);
    }
}
LG 4247 [清华集训2012]序列操作
comment评论
Search
search