线段树练手好题。
直接上线段树五问：
维护的信息是什么？
由于 \(c\le 20\)，我们不妨对线段树的每个节点维护一个 \(f_k\) 表示在对应区间里选择 \(k\) 个数相乘的所有方案的和。
怎么合并两个信息？
对于两个信息 \(f_k\) 和 \(g_k\)，设合并后的信息为 \(h_i\)，根据乘法分配律，\(f_ig_j\) 会对 \(h_{i+j}\) 产生贡献，直接 \(O(c^2)\) 暴力算即可。
维护的标记是什么？
参考线段树 2，我们可以维护区间取反标记和区间加标记，优先级为先取反再加。
怎么合并两个标记？
按先取反再加的顺序给标记施加影响就行了。
怎么打标记于信息？
区间取反
不难发现只要对于所有 \(f_{2k+1}\) 取反就行了。
区间加
设加上的数为 \(x\)。
考虑 \(x^i\) 的贡献。由于次数为 \(k\)，所以有 \(k-i\) 个数是固定的，剩余的方案数即为 \({n-i\choose i}\)，总的式子即为：
\[f_k=\sum_{i=0}^kx^i{n-i\choose i}f_{k-i} \]细节
- 模数不是质数，需要使用递推的方法求组合数。
- 注意初始序列和加上的数可能为负数。
#include <iostream>
using namespace std;
using LL = long long;
const int kN = 5e4 + 1, kC = 21;
const LL kM = 19940417;
struct T {
bool n;
LL a;
T(bool n = 0, LL a = 0) : n(n), a((a % kM + kM) % kM) {}
const T operator+=(const T &o) {
if (o.n) {
n ^= 1, a = (kM - a) % kM;
}
a = (a + o.a) % kM;
return *this;
}
};
LL _c[kN][kC];
LL C(int n, int m) {
if (m < 0 || m > n) {
return 0;
}
if (_c[n][m]) {
return _c[n][m];
}
if (m == 0 || m == n) {
return _c[n][m] = 1;
}
return _c[n][m] = (C(n - 1, m - 1) + C(n - 1, m)) % kM;
}
struct I {
LL c[kC];
int n;
I() { fill(c, c + kC, 0), c[n = 0] = 1; }
const I operator+(const I &o) const {
I s;
s.n = n + o.n, s.c[0] = 0;
for (int i = 0; i < kC && i <= n; ++i) {
for (int j = 0; i + j < kC && j <= o.n; ++j) {
s.c[i + j] = (s.c[i + j] + c[i] * o.c[j] % kM) % kM;
}
}
return s;
}
const I operator+=(const T &o) {
if (o.n) {
for (int i = 1; i < kC && i <= n; i += 2) {
c[i] = (kM - c[i]) % kM;
}
}
LL _c[kC], px[kC];
copy(c, c + kC, _c);
for (int i = px[0] = 1; i < kC && i <= n; ++i) {
px[i] = px[i - 1] * o.a % kM;
}
for (int i = 1; i < kC && i <= n; ++i) {
c[i] = 0;
for (int j = 0; j <= i; ++j) {
c[i] = (c[i] + _c[i - j] * px[j] % kM * C(n - j, j) % kM) % kM;
}
}
return *this;
}
};
struct E {
I v;
T t;
int l, r;
const E operator+=(const T &o) {
v += o, t += o;
return *this;
}
} e[kN << 2];
void B(int x, int l, int r) {
e[x].l = l, e[x].r = r;
if (l == r) {
LL v;
cin >> v;
e[x].v.n = 1, e[x].v += T(0, v);
return;
}
int m = l + r >> 1;
B(x * 2, l, m), B(x * 2 + 1, m + 1, r);
e[x].v = e[x * 2].v + e[x * 2 + 1].v;
}
void U(int x, int l, int r, T t) {
if (e[x].l == l && e[x].r == r) {
e[x] += t;
return;
}
e[x * 2] += e[x].t, e[x * 2 + 1] += e[x].t, e[x].t = T();
if (l <= e[x * 2].r) {
U(x * 2, l, min(r, e[x * 2].r), t);
}
if (e[x * 2 + 1].l <= r) {
U(x * 2 + 1, max(l, e[x * 2 + 1].l), r, t);
}
e[x].v = e[x * 2].v + e[x * 2 + 1].v;
}
I Q(int x, int l, int r) {
if (e[x].l == l && e[x].r == r) {
return e[x].v;
}
e[x * 2] += e[x].t, e[x * 2 + 1] += e[x].t, e[x].t = T();
I s;
if (l <= e[x * 2].r) {
s = s + Q(x * 2, l, min(r, e[x * 2].r));
}
if (e[x * 2 + 1].l <= r) {
s = s + Q(x * 2 + 1, max(l, e[x * 2 + 1].l), r);
}
e[x].v = e[x * 2].v + e[x * 2 + 1].v;
return s;
}
int n, q;
int main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> q;
B(1, 1, n);
for (int l, r, v; q--;) {
char o;
cin >> o >> l >> r;
if (o == 'I') {
cin >> v;
U(1, l, r, T(0, v));
} else if (o == 'R') {
U(1, l, r, T(1, 0));
} else {
cin >> v;
I s = Q(1, l, r);
cout << s.c[v] << '\n';
}
}
return 0;
}