[清华集训]序列操作

Myth丶恋晨 2023-10-11 11:19 23阅读 0赞

[题目][Link 1]

在\\(\\operatorname\{NOIP\}\\)停办的日子发篇博客纪念一下

发现这个\\(c\\leq \\min(20,r-l+1)\\)，显然可以把\\(0\\)到\\(20\\)的答案都存一下，线段树合并两个区间就是直接做一个卷积

考虑区间加操作，设\\(f\_i\\)表示当前区间里所有长度为\\(i\\)的子序列乘积的和，我们考虑每一个子序列对这个的贡献，有

\\\[f\_i=\\sum\_\{j=0\}^if\_j\\binom\{len-j\}\{i-j\}c^\{i-j\}\\\]

就是考虑一个原来长度为\\(j\\)的子序列，只有乘上\\(c^\{i-j\}\\)才能对长度为\\(i\\)的子序列产生贡献，同时对于剩下的\\(len-j\\)个数我们再随便选出\\(i-j\\)个就能构成长度为\\(j\\)的子序列了，于是再乘上\\(\\binom\{len-j\}\{i-j\}\\)

这个东西也可以直接\\(20^2\\)算出来

对于取反，我们只需要把长度为奇数的子序列取一个反就好了，同时把加法标记取反

于是就以\\(O(20^2m\\operatorname\{logn\})\\)的复杂度做完了这道题

代码

#include<bits/stdc++.h>
    #define re register
    #define LL long long
    #define min std::min
    inline int read() {
        char c=getchar();int x=0,r=1;
        while(c<'0'||c>'9') {if(c=='-') r=-1;c=getchar();}
        while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return r*x;
    }
    const int maxn=5e4+5;
    const int mod=19940417;
    int c[maxn][21];
    int l[maxn*3],r[maxn*3],tag[maxn*3],rev[maxn*3];
    int dp[maxn*3][21],h[21],pw[21],ans[21],n,m;
    inline int C(int n,int m) {return m>n?0:c[n][m];}
    inline void merge(int *f,int *g,int T) {
        for(re int i=0;i<=T;i++) h[i]=0;
        for(re int i=0;i<=T;i++)
            for(re int j=0;i+j<=T;j++)
                h[i+j]=(h[i+j]+1ll*f[i]*g[j]%mod)%mod;
        for(re int i=0;i<=T;i++) f[i]=h[i];
    }
    inline void pushup(int x) {
        for(re int i=0;i<=20;i++) 
            dp[x][i]=dp[x<<1][i];
        merge(dp[x],dp[x<<1|1],20);
    }
    void build(int x,int y,int i) {
        l[i]=x,r[i]=y;
        if(x==y) {
            dp[i][0]=1;dp[i][1]=(read()+mod)%mod;return;
        }
        int mid=x+y>>1;
        build(x,mid,i<<1),build(mid+1,y,i<<1|1);
        pushup(i);
    }
    void solve(int *f,int v,int len) {
        int T=min(20,len);
        for(re int i=1;i<=T;i++) pw[i]=1ll*pw[i-1]*v%mod;
        for(re int i=T;i;--i) 
            for(re int j=i-1;j>=0;--j)
                f[i]=(f[i]+1ll*f[j]*pw[i-j]%mod*C(len-j,i-j)%mod)%mod;
    }
    inline void pushdown(int x) {
        if(rev[x]) {
            rev[x<<1|1]^=1,rev[x<<1]^=1;
            tag[x<<1|1]=(mod-tag[x<<1|1])%mod;
            tag[x<<1]=(mod-tag[x<<1])%mod;
            for(re int i=1;i<=20;i+=2)
                dp[x<<1][i]=(mod-dp[x<<1][i])%mod,
                dp[x<<1|1][i]=(mod-dp[x<<1|1][i])%mod;
            rev[x]=0;
        }
        if(tag[x]) {
            tag[x<<1]=(tag[x<<1]+tag[x])%mod;
            tag[x<<1|1]=(tag[x<<1|1]+tag[x])%mod;
            solve(dp[x<<1],tag[x],r[x<<1]-l[x<<1]+1);
            solve(dp[x<<1|1],tag[x],r[x<<1|1]-l[x<<1|1]+1);
            tag[x]=0;
        }
    }
    void add(int x,int y,int v,int i) {
        if(x<=l[i]&&y>=r[i]) {
            solve(dp[i],v,r[i]-l[i]+1);
            tag[i]=(tag[i]+v)%mod;
            return;
        }
        pushdown(i);
        int mid=l[i]+r[i]>>1;
        if(x<=mid) add(x,y,v,i<<1);
        if(y>mid) add(x,y,v,i<<1|1);
        pushup(i);
    }
    void change(int x,int y,int i) {
        if(x<=l[i]&&y>=r[i]) {
            rev[i]^=1;
            tag[i]=(mod-tag[i])%mod;
            for(re int j=1;j<=20;j+=2)
                dp[i][j]=(mod-dp[i][j])%mod;
            return;
        }
        pushdown(i);
        int mid=l[i]+r[i]>>1;
        if(x<=mid) change(x,y,i<<1);
        if(y>mid) change(x,y,i<<1|1);
        pushup(i);
    } 
    void query(int x,int y,int v,int i) {
        if(x<=l[i]&&y>=r[i]) {
            merge(ans,dp[i],v);
            return;
        }
        pushdown(i);
        int mid=l[i]+r[i]>>1;
        if(x<=mid) query(x,y,v,i<<1);
        if(y>mid) query(x,y,v,i<<1|1);
    }
    int main() {
        n=read(),m=read();build(1,n,1);
        for(re int i=0;i<=n;i++) c[i][0]=1;
        for(re int i=1;i<=n;i++)
            for(re int j=1;j<=min(i,20);j++)
                c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
        char op[4];int x,y,v;ans[0]=pw[0]=1;
        while(m--) {
            scanf("%s",op);x=read(),y=read();
            if(op[0]=='I') {
                v=read();v=(v%mod+mod)%mod;
                add(x,y,v,1);
            }
            if(op[0]=='Q') {
                v=read();v=(v%mod+mod)%mod;
                for(re int i=1;i<=20;i++) ans[i]=0;
                query(x,y,v,1);
                printf("%d\n",ans[v]);
            }
            if(op[0]=='R') change(x,y,1);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/asuldb/p/11366167.html

[Link 1]: https://www.luogu.org/problem/P4247