[文章目录]
Description
有一个长度为n的序列，有三个操作1.I a b c表示将[a,b]这一段区间的元素集体增加c，2.R a b表示将[a,b]区间内所有元素变成相反数，3.Q a b c表示询问[a,b]这一段区间中选择c个数相乘的所有方案的和mod 19940417 的值。n,q<=50000 c<=20
由于c只有20，我们可以O(c^2)区间合并，取相反数直接看c的奇偶性修改，区间加c的话可以枚举c的幂次，统计答案。线段树即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
#define N 51000
const ll mod=19940417;
int n,m,w[N],C[N][21];
struct node
{
ll a[21]; int len,lz,tur;
node(){memset(a,0,sizeof a); a[0]=1; tur=lz=0;}
node operator * (const node z)
{
node re; int i,j;
for(i=1;i<=20;++i)
for(j=0;j<=i;++j)
re.a[i]=(re.a[i]+a[j]*z.a[i-j])%mod;
re.len=len+z.len;
return re;
}
node operator + (const int z)
{
node re=*this; int i,j; ll po=1;
for(i=1;i<=20;++i)
{
po=po*z%mod;
for(j=i;j<=20;++j)
re.a[j]=(re.a[j]+po*a[j-i]%mod*C[len-(j-i)][i])%mod;
}
return re;
}
void oppo() {for(int i=1;i<=20;i+=2) a[i]=(mod-a[i])%mod; lz=(mod-lz)%mod;}
}t[N<<2];
void pushdown(int pos)
{
if(t[pos].tur)
{
t[pos<<1].tur^=1; t[pos<<1].oppo();
t[pos<<1|1].tur^=1; t[pos<<1|1].oppo();
t[pos].tur=0;
}
if(t[pos].lz)
{
t[pos<<1]=t[pos<<1]+t[pos].lz;
t[pos<<1].lz=(t[pos<<1].lz+t[pos].lz)%mod;
t[pos<<1|1]=t[pos<<1|1]+t[pos].lz;
t[pos<<1|1].lz=(t[pos<<1|1].lz+t[pos].lz)%mod;
t[pos].lz=0;
}
}
void build(int pos,int l,int r)
{
t[pos].len=r-l+1;
if(l==r){t[pos].a[1]=w[l]; return ;}
int mid=(l+r)>>1;
build(pos<<1,l,mid); build(pos<<1|1,mid+1,r);
t[pos]=t[pos<<1]*t[pos<<1|1];
}
void add(int pos,int l,int r,int x,int y,int z)
{
if(x<=l&&y>=r)
{
t[pos]=t[pos]+z;
t[pos].lz=(t[pos].lz+z)%mod;
return ;
}
int mid=(l+r)>>1; pushdown(pos);
if(x<=mid) add(pos<<1,l,mid,x,y,z);
if(y>mid) add(pos<<1|1,mid+1,r,x,y,z);
t[pos]=t[pos<<1]*t[pos<<1|1];
}
void oppo(int pos,int l,int r,int x,int y)
{
if(x<=l&&y>=r)
{
t[pos].oppo();
t[pos].tur^=1;
return ;
}
int mid=(l+r)>>1; pushdown(pos);
if(x<=mid) oppo(pos<<1,l,mid,x,y);
if(y>mid) oppo(pos<<1|1,mid+1,r,x,y);
t[pos]=t[pos<<1]*t[pos<<1|1];
}
node query(int pos,int l,int r,int x,int y)
{
if(x<=l&&y>=r) return t[pos];
int mid=(l+r)>>1; pushdown(pos);
if(y<=mid) return query(pos<<1,l,mid,x,y);
if(x>mid) return query(pos<<1|1,mid+1,r,x,y);
return query(pos<<1,l,mid,x,y)*query(pos<<1|1,mid+1,r,x,y);
}
int main()
{
scanf("%d%d",&n,&m);
int i,j;
C[0][0]=1;
for(i=1;i<=n;++i)
{
C[i][0]=1;
for(j=1;j<=20&&j<=i;++j)
C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
for(i=1;i<=n;++i) scanf("%d",w+i),w[i]=(w[i]%mod+mod)%mod;
build(1,1,n);
char op[10]; int l,r,x;
while(m--)
{
scanf("%s",op);
if(op[0]=='I') scanf("%d%d%d",&l,&r,&x),x=(x%mod+mod)%mod,add(1,1,n,l,r,x);
if(op[0]=='R') scanf("%d%d",&l,&r),oppo(1,1,n,l,r);
if(op[0]=='Q') scanf("%d%d%d",&l,&r,&x),printf("%lld\n",query(1,1,n,l,r).a[x]);
}
return 0;
}