题面
Sol
线段树，维护一个长度为(20)的数组，每次合并时就是左右儿子做个卷积
区间加法
二项式展开
用(len)表示区间长度，加的(x)的贡献组合数算一下就好了
看代码就知道了
# include <bits/stdc++.h>
# define RG register
# define IL inline
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
const int _(5e4 + 5);
const int Zsy(19940417);
IL ll Input(){
RG ll x = 0, z = 1; RG char c = getchar();
for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
return x * z;
}
int n, q, c[_][21];
struct Segment{
int tag, rev, s[21];
} T[_ << 2];
int tmp[21], ans[21];
IL void Update(RG int x){
RG int ls = x << 1, rs = x << 1 | 1;
for(RG int i = 0; i <= 20; ++i){
T[x].s[i] = 0;
for(RG int j = 0; j <= i; ++j)
(T[x].s[i] += 1LL * T[ls].s[j] * T[rs].s[i - j] % Zsy) %= Zsy;
}
}
IL void Adjust1(RG int x){
T[x].rev ^= 1, T[x].tag = Zsy - T[x].tag;
for(RG int i = 1; i < 20; i += 2) T[x].s[i] = Zsy - T[x].s[i];
}
IL void Adjust2(RG int x, RG int v, RG int l, RG int r){
(T[x].tag += v) %= Zsy;
RG int len = r - l + 1;
for(RG int i = 1; i <= 20; ++i){
tmp[i] = 0;
for(RG int j = i, g = 1; ~j; --j, g = 1LL * g * v % Zsy)
(tmp[i] += 1LL * T[x].s[j] * c[len - j][i - j] % Zsy * g % Zsy) %= Zsy;
}
for(RG int i = 1; i <= 20; ++i) T[x].s[i] = tmp[i];
}
IL void Pushdown(RG int x, RG int l, RG int r){
if(T[x].rev){
Adjust1(x << 1), Adjust1(x << 1 | 1);
T[x].rev ^= 1;
}
if(T[x].tag){
RG int mid = (l + r) >> 1;
Adjust2(x << 1, T[x].tag, l, mid);
Adjust2(x << 1 | 1, T[x].tag, mid + 1, r);
T[x].tag = 0;
}
}
IL void Build(RG int x, RG int l, RG int r){
T[x].s[0] = 1;
if(l == r){
T[x].s[1] = (Input() % Zsy + Zsy) % Zsy;
return;
}
RG int mid = (l + r) >> 1;
Build(x << 1, l, mid), Build(x << 1 | 1, mid + 1, r);
Update(x);
}
IL void Modify1(RG int x, RG int l, RG int r, RG int L, RG int R){
if(L <= l && R >= r){
Adjust1(x);
return;
}
Pushdown(x, l, r);
RG int mid = (l + r) >> 1;
if(L <= mid) Modify1(x << 1, l, mid, L, R);
if(R > mid) Modify1(x << 1 | 1, mid + 1, r, L, R);
Update(x);
}
IL void Modify2(RG int x, RG int l, RG int r, RG int L, RG int R, RG int v){
if(L <= l && R >= r){
Adjust2(x, v, l, r);
return;
}
Pushdown(x, l, r);
RG int mid = (l + r) >> 1;
if(L <= mid) Modify2(x << 1, l, mid, L, R, v);
if(R > mid) Modify2(x << 1 | 1, mid + 1, r, L, R, v);
Update(x);
}
IL void Calc(RG int x){
for(RG int i = 1; i <= 20; ++i){
tmp[i] = 0;
for(RG int j = 0; j <= i; ++j)
(tmp[i] += 1LL * ans[j] * T[x].s[i - j] % Zsy) %= Zsy;
}
for(RG int i = 1; i <= 20; ++i) ans[i] = tmp[i];
}
IL void Query(RG int x, RG int l, RG int r, RG int L, RG int R){
if(L <= l && R >= r){
Calc(x);
return;
}
Pushdown(x, l, r);
RG int mid = (l + r) >> 1;
if(L <= mid) Query(x << 1, l, mid, L, R);
if(R > mid) Query(x << 1 | 1, mid + 1, r, L, R);
}
int main(RG int argc, RG char *argv[]){
n = Input(), q = Input(), c[0][0] = 1;
for(RG int i = 1; i <= n; ++i){
c[i][0] = 1;
for(RG int j = 1; j <= 20; ++j)
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % Zsy;
}
Build(1, 1, n);
while(q--){
RG char op; scanf(" %c", &op);
RG int l = Input(), r = Input(), v;
if(op == 'I') v = Input(), Modify2(1, 1, n, l, r, (v % Zsy + Zsy) % Zsy);
else if(op == 'R') Modify1(1, 1, n, l, r);
else{
v = Input(), Fill(ans, 0), ans[0] = 1;
Query(1, 1, n, l, r);
printf("%d
", ans[v]);
}
}
return 0;
}