BZOJ2962: 序列操作

題目大意：給定n個數，要求支援區間加，區間取相反數，區間查詢任意選c(c<=20)個數的所有方案中乘積的和

和維護k次方的和很像，想要維護選c個數，就要把選1~c個數的方案全部維護出來

這樣當合并兩個區間的時候(pushup)，隻需要枚舉左右區間分别取了幾個數即可

現在考慮兩種修改操作：

1.區間取相反數

發現這種操作隻會影響區間選奇數個數的情況，把這些答案全部變成相反數即可

2.區間加

這個就比較厲害了，首先我們考慮c=2的情況

設總個數為len，這些數分别為 a1,a2...alen ，則

∑i=1len∑j=1i−1(ai+v)(aj+v)=∑i=1len∑j=1i−1(aiaj+v2+(ai+aj)v)=∑i=1len∑j=1i−1aiaj+C2lenv2+C1len−1∑i=1lenaiv

同理可求得c=3時的式子，是以隻需要預處理出組合數，就可以遞推了

總時間複雜度 O(MlogN∗202)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 
using namespace std;
struct ppp{int a[],len;};
int a[N];
int C[N][];
int mod=;
int l[N<<],r[N<<],t[N<<];
bool rev[N<<];
ppp w[N<<];
ppp ret;
ppp operator +(const ppp &x,const ppp &y)
{
    ret.len=x.len+y.len;
    memset(ret.a,,sizeof(ret.a));
    int i,j;
    for(i=;i<=;i++)
    for(j=;j<=-i;j++)
    ret.a[i+j]=((long long)x.a[i]*y.a[j]+ret.a[i+j])%mod;
    return ret;
}
void pup(int x){w[x]=w[x<<]+w[x<<|];}
void pudrev(int x)
{
    int i;
    rev[x]^=;
    t[x]=(mod-t[x])%mod;
    for(i=;i<=;i+=)
    w[x].a[i]=(mod-w[x].a[i])%mod;
}
int ksm(int d,int c)
{
    int ret=;
    while(c)
    {
        if(c&) ret=(long long)ret*d%mod;
        d=(long long)d*d%mod;c/=;
    }
    return ret;
}
void pudadd(int x,int v)
{
    t[x]=(t[x]+v)%mod;
    int i,j,l=w[x].len;
    for(i=min(,l);i>=;i--)
    for(j=i-;j>=;j--)
    w[x].a[i]=((long long)ksm(v,i-j)*C[l-j][i-j]%mod*w[x].a[j]+w[x].a[i])%mod;
}
void pud(int x)
{
    int i,j;
    if(rev[x])
    {
        pudrev(x<<);
        pudrev(x<<|);
        rev[x]=;
    }
    if(t[x])
    {
        pudadd(x<<,t[x]);
        pudadd(x<<|,t[x]);
        t[x]=;
    }
}
void build(int now,int ll,int rr)
{
    l[now]=ll;r[now]=rr;
    if(ll==rr)
    {
        w[now].len=;
        w[now].a[]=;
        w[now].a[]=a[ll];
        return;
    }
    int mid=(ll+rr)>>;
    build(now<<,ll,mid);
    build(now<<|,mid+,rr);
    pup(now);
}
void change(int now,int ll,int rr,int v)
{
    if(l[now]==ll&&r[now]==rr)
    {
        pudadd(now,v);
        return;
    }
    pud(now);
    int mid=(l[now]+r[now])>>;
    if(rr<=mid) change(now<<,ll,rr,v);
    else if(ll>mid) change(now<<|,ll,rr,v);
    else change(now<<,ll,mid,v),change(now<<|,mid+,rr,v);
    pup(now);
}
void reverse(int now,int ll,int rr)
{
    if(l[now]==ll&&r[now]==rr)
    {
        pudrev(now);
        return;
    }
    pud(now);
    int mid=(l[now]+r[now])>>;
    if(rr<=mid) reverse(now<<,ll,rr);
    else if(ll>mid) reverse(now<<|,ll,rr);
    else reverse(now<<,ll,mid),reverse(now<<|,mid+,rr);
    pup(now);
}
ppp check(int now,int ll,int rr)
{
    if(ll==l[now]&&rr==r[now]) return w[now];
    pud(now);
    int mid=(l[now]+r[now])>>;
    if(rr<=mid) return check(now<<,ll,rr);
    else if(ll>mid) return check(now<<|,ll,rr);
    else return check(now<<,ll,mid)+check(now<<|,mid+,rr);
}
int main()
{
    int n,q;
    scanf("%d%d",&n,&q);
    int i,j,x,y,z;
    C[][]=;
    for(i=;i<=n;i++)
    {
        C[i][]=;
        for(j=;j<=;j++)
        C[i][j]=(C[i-][j-]+C[i-][j])%mod;
    }
    for(i=;i<=n;i++)
    scanf("%d",&a[i]);
    build(,,n);
    char s[];
    while(q--)
    {
        scanf("%s%d%d",s,&x,&y);
        if(s[]=='I')
        {
            scanf("%d",&z);
            change(,x,y,(z%mod+mod)%mod);
        }
        else if(s[]=='R') reverse(1,x,y);
        else
        {
            scanf("%d",&z);
            printf("%d\n",check(,x,y).a[z]);
        }
    }
}