题目描述
有一个长度为 n n 的序列，有三个操作：
I a b c表示将 [a,b][a,b] 这一段区间的元素集体增加 c c ；
R a b表示将 [a,b][a,b] 区间内所有元素变成相反数；
Q a b c表示询问 [a,b] [ a , b ] 这一段区间中选择 c c 个数相乘的所有方案的和 mod 19940417mod 19940417 的值。
输入输出格式
输入格式：
第一行两个数 n, qn,q 表示序列长度和操作个数。
第二行 nn 个非负整数，表示序列。
接下来 qq 行每行输入一个操作I a b c或者R a b或者Q a b c，意义如题目描述。
输出格式：
对于每个询问，输出选出 c 个数相乘的所有方案的和 mod 19940417 m o d 19940417 的值。
输入输出样例
输入样例#1：
5 5
1 2 3 4 5
I 2 3 1
Q 2 4 2
R 1 5
I 1 3 -1
Q 1 5 1
输出样例#1：
40
19940397
说明
样例说明：
做完第一个操作序列变为1 3 4 4 5。
第一次询问结果为 3×4+3×4+4×4=40 。
做完R操作变成-1 -3 -4 -4 -5。
做完I操作变为-2 -4 -5 -4 -5。
第二次询问结果为 −2−4−5−4−5=−20 。
数据范围：
对于100%的数据， n≤50000,q≤50000 n ≤ 50000 , q ≤ 50000 ，初始序列的元素的绝对值 \leq 109≤109 ，保证 [a,b] [ a , b ] 是一个合法区间，I操作中 ∣∣c∣≤109 ∣ c ∣≤ 10 9 ，Q操作中 1≤c≤min(b−a+1,20) 1 ≤ c ≤ m i n ( b − a + 1 , 20 ) 。
分析：首先因为查询 c c 很小，所以我们可以维护[0,20][0,20]所有的 c c 。
区间加kk答案应该怎样修改呢？
对于一个长度为 3 3 的序列[a1,a2,a3][a1,a2,a3]会变为 [a1+k,a2+k,a3+k] [ a 1 + k , a 2 + k , a 3 + k ] 。所以这个序列新的值为， a1∗a2∗a3+k∗(a1∗a2+a1∗a3+a2∗a3)+k2∗(a1+a2+a3)+k3 a 1 ∗ a 2 ∗ a 3 + k ∗ ( a 1 ∗ a 2 + a 1 ∗ a 3 + a 2 ∗ a 3 ) + k 2 ∗ ( a 1 + a 2 + a 3 ) + k 3 。
观察可以得到，一个序列的新值等于其任意一个子序列的和* kx k x ，其中 x x 为原序列长-子序列长。那对于区间内所有的长度为ii序列，每一个长度为 j(j<=i) j ( j <= i ) 的序列都对该序列有贡献。假设区间长度为 len l e n ，区间 c c 个数相乘结果为f[c]f[c]，长度为 j j 的序列可以通过在len−jlen−j中选 i−j i − j 个数来贡献长度为 i i 的序列，因为每个长度为jj的贡献次数一样，所以直接可以用 f[j]∗(len−ji−j)∗ki−j f [ j ] ∗ ( l e n − j i − j ) ∗ k i − j 来贡献 i i 。转移方程为，
f[i]=∑j=0if[j]∗(len−ji−j)∗ki−jf[i]=∑j=0if[j]∗(len−ji−j)∗ki−j
合并区间也就是左边选 i i 个数，右边选jj个数的和相乘，就是新区间 i+j i + j 个数的和。
区间取反会改变奇数 i i 的f[i]f[i]，暴力处理就可以了。
复杂度为 O(202∗nlogn) O ( 20 2 ∗ n l o g n )
写完只会疯狂RE，对拍有没错，最后暴力开到50w就过了，我看标都是20w。。。
代码：
#include <iostream>
#include <cmath>
#include <cstdio>
#define LL long long
const int maxn=;
const LL mod=;
using namespace std;
struct rec{
LL f[];
};
struct tree{
rec ans;
LL lazy;
int rev;
}t[];
int a[maxn];
LL c[maxn][];
LL power[];
int n,test,x,y,z;
LL k;
rec merge(rec x,rec y)
{
rec z;
for (int i=;i<=;i++)
{
z.f[i]=;
for (int j=;j<=i;j++)
{
z.f[i]=(z.f[i]+x.f[j]*y.f[i-j]%mod)%mod;
}
}
return z;
}
void build(int p,int l,int r)
{
if (l==r)
{
t[p].ans.f[]=;
t[p].ans.f[]=(a[l]%mod+mod)%mod;
return;
}
int mid=(l+r)/;
build(p*2,l,mid);
build(p*2+,mid+,r);
t[p].ans=merge(t[p*2].ans,t[p*2+].ans);
}
void change(int p,int len,LL k)
{
power[]=;
for (int i=;i<=;i++) power[i]=(power[i-]*k)%mod;
for (int i=;i>=;i--)
{
for (int j=;j<i;j++)
{
t[p].ans.f[i]=(t[p].ans.f[i]+t[p].ans.f[j]*power[i-j]%mod*c[len-j][i-j]%mod)%mod;
}
}
}
void cleanrev(int p)
{
for (int i=;i<=;i++) if (i%2) t[p].ans.f[i]=(mod-t[p].ans.f[i])%mod;
}
void mark(int p,int l,int r)
{
int mid=(l+r)/;
if (t[p].rev)
{
t[p*2].rev^=;
t[p*2].lazy=(mod-t[p*2].lazy)%mod;
cleanrev(p*2);
t[p*2+].rev^=;
t[p*2+].lazy=(mod-t[p*2+].lazy)%mod;
cleanrev(p*2+);
t[p].rev^=;
}
if (t[p].lazy)
{
t[p*2].lazy=(t[p*2].lazy+t[p].lazy)%mod;
t[p*2+].lazy=(t[p*2+].lazy+t[p].lazy)%mod;
change(p*2,mid-l+,t[p].lazy);
change(p*2+,r-mid,t[p].lazy);
t[p].lazy=;
}
}
void ins(int p,int l,int r,int x,int y,LL k)
{
if ((l==x) && (r==y))
{
t[p].lazy=(t[p].lazy+k)%mod;
change(p,r-l+,k);
return;
}
int mid=(l+r)/;
mark(p,l,r);
if (y<=mid) ins(p*2,l,mid,x,y,k);
else if (x>mid) ins(p*2+,mid+,r,x,y,k);
else
{
ins(p*2,l,mid,x,mid,k);
ins(p*2+,mid+,r,mid+,y,k);
}
t[p].ans=merge(t[p*2].ans,t[p*2+].ans);
}
void rep(int p,int l,int r,int x,int y)
{
if ((l==x) && (r==y))
{
t[p].rev^=;
cleanrev(p);
LL now=(mod-t[p].lazy)%mod;
t[p].lazy=now;
return;
}
int mid=(l+r)/;
mark(p,l,r);
if (y<=mid) rep(p*2,l,mid,x,y);
else if (x>mid) rep(p*2+,mid+,r,x,y);
else
{
rep(p*2,l,mid,x,mid);
rep(p*2+,mid+,r,mid+,y);
}
t[p].ans=merge(t[p*2].ans,t[p*2+].ans);
}
rec query(int p,int l,int r,int x,int y)
{
if ((l==x) && (r==y)) return t[p].ans;
int mid=(l+r)/;
mark(p,l,r);
if (y<=mid) return query(p*2,l,mid,x,y);
else if (x>mid) return query(p*2+,mid+,r,x,y);
else return merge(query(p*2,l,mid,x,mid),query(p*2+,mid+,r,mid+,y));
}
int main()
{
// freopen("data.in","r",stdin);
// freopen("mypout.out","w",stdout);
scanf("%d%d",&n,&test);
for (int i=;i<=n;i++) scanf("%lld",&a[i]);
c[][]=;
for (int i=;i<=n;i++)
{
c[i][]=;
for (int j=;j<=;j++) c[i][j]=(c[i-][j-]+c[i-][j])%mod;
}
build(,,n);
char s[];
for (int i=;i<=test;i++)
{
scanf("%s",s);
if (s[]=='I')
{
scanf("%d%d%lld",&x,&y,&k);
k=(k%mod+mod)%mod;
ins(,,n,x,y,k);
}
if (s[]=='R')
{
scanf("%d%d",&x,&y);
rep(,,n,x,y);
}
if (s[]=='Q')
{
scanf("%d%d%d",&x,&y,&z);
rec d=query(,,n,x,y);
printf("%lld\n",d.f[z]);
}
}
}