P4247 [清华集训2012]序列操作

· · 题解

题传

调了一天终于过了，写篇题解庆祝

前两个操作是个 板子，我们考虑操作 3。

注意到 c \le 20，不妨设 f_i 为选 i 个数相乘的方案和。

显然有 f_i=\sum_{j=0}^{i} f_{ls, j} \times f_{rs, i-j}，暴力时向上 O(c^2) 合并，那么没有操作 1、2 的世界完成了！！1

考虑加上操作 1 怎么做，方案中原本的一个和大概长这个样子：

s_c=\prod_{i=1}^{c} x_i

每个数都加上一个 v：

s'_c=\prod_{i=1}^{c} (x_i+v)

类似于二项式定理，将其拆解：

s'_c=\sum_{cnt=0}^{c} (\prod_{p_1<p_2<...p_{cnt}} x_{p}) \times v^{c-cnt}

不难发现括号里面那堆东西就是旧的 f_{cnt}，即：

s'_c=\sum_{cnt=0}^{c} f_{cnt} \times v^{c-cnt}

也是暴力合并。

对于操作二，直接将奇数个相乘的、以及加法标记取反即可。

注意要先下传乘法标记。

时间复杂度 O(n c^2 \log n)。

Code：

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int mo=19940417;
const int R=20;
inline int read(){
    char ch=getchar();int x=0, f=1;
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}
inline int mod(int x){return (x%mo+mo)%mo;}
namespace Solution{
    const int N=5e4+5;
    int n, m, a[N], C[N][25];
    struct node{
        node(){at=mt=len=0, f[0]=1;for(int i=1; i<=20; i++) f[i]=0;}
        int f[25], len;
        int at, mt;
    }S;
    node add(node l, node r){
        node c=S;
        c.len=l.len+r.len;
        for(int i=1; i<=min(R, c.len); i++)
            for(int j=0; j<=i; j++)
                c.f[i]=mod(c.f[i]+1ll*l.f[j]*r.f[i-j]%mo);
        return c;
    }
    node d[N*30];
    struct SegmentTree{
        #define ls k<<1
        #define rs k<<1|1
        #define mid (l+r>>1)
        void upd1(int k, int v){//区间加 
            int t=min(R, d[k].len);
            for(int i=t; i; i--)
                for(int j=1, st=v; j<=i; j++, st=1ll*st*v%mo)
                    d[k].f[i]=mod(d[k].f[i]+1ll*d[k].f[i-j]*st%mo*C[d[k].len-i+j][j]%mo);
            d[k].at=mod(d[k].at+v);
        }
        void upd2(int k){//区间取反
            int t=min(R, d[k].len);
            for(int i=1; i<=t; i++)
                if(i&1) d[k].f[i]=mod(-d[k].f[i]);
            d[k].at=mod(-d[k].at);
            d[k].mt^=1; 
        }
        void pushdown(int k){
            if(d[k].mt) upd2(ls), upd2(rs);
            if(d[k].at) upd1(ls, d[k].at), upd1(rs, d[k].at);
            d[k].at=0, d[k].mt=0;
            return ;
        }
        void build(int k, int l, int r){
            d[k]=S;d[k].len=r-l+1;
            if(l==r){d[k].f[1]=a[l&r];return ;}
            build(ls, l, mid), build(rs, mid+1, r);
            d[k]=add(d[ls], d[rs]);
        }
        void change(int k, int l, int r, int x, int y, int v, bool flg){
//          if(flg) printf(">>%d %d\n", k, v);
            if(x<=l&&r<=y) return flg?upd1(k, v):upd2(k);pushdown(k);
            if(x<=mid) change(ls, l, mid, x, y, v, flg);
            if(mid<y) change(rs, mid+1, r, x, y, v, flg);
            d[k]=add(d[ls], d[rs]);
        }
        node query(int k, int l, int r, int x, int y){
            if(x<=l&&r<=y) return d[k];pushdown(k);
            if(y<=mid) return query(ls, l, mid, x, y);
            if(x>mid) return query(rs, mid+1, r, x, y);
            return add(query(ls, l, mid, x, y), query(rs, mid+1, r, x, y));
        }
        void debug(){
            for(int j=1; j<=n; j++) printf("---%d",d[1].f[j]);puts("");
        }
        #undef ls
        #undef rs
        #undef mid
    }Chtholly;  
    signed work(){
        n=read(), m=read();
        for(int i=0; i<=20; i++){
            C[i][0]=1;
            for(int j=1; j<=i; j++) 
                C[i][j]=mod(C[i-1][j]+C[i-1][j-1]);
        }
        for(int i=21; i<=n; i++){
            C[i][0]=1;
            for(int j=1; j<=20; j++) 
                C[i][j]=mod(C[i-1][j]+C[i-1][j-1]);
        }
        for(int i=1; i<=n; i++)
            a[i]=mod(read());
        Chtholly.build(1, 1, n);//Chtholly.debug();
        for(int i=1; i<=m; i++){
            char opt=getchar();
            int a, b, c;
            while(opt!='I'&&opt!='R'&&opt!='Q') opt=getchar();
            if(opt=='I') 
                a=read(), b=read(), c=mod(read()), Chtholly.change(1, 1, n, a, b, c, 1);
            else if(opt=='R')
                a=read(), b=read(), Chtholly.change(1, 1, n, a, b, 0, 0);
            else 
                a=read(), b=read(), c=read(),
                printf("%d\n", Chtholly.query(1, 1, n, a, b).f[c]);
            //Chtholly.debug();
        }
        return 0;
    }
}
signed main(){
    Solution :: work();
    return 0;
}