题解 【P4247 [清华集训2012]序列操作】

由于事奔着线段树来的所以跳过怎么想到线段树这一部分

看到这题，想到对于线段树的节点维护一个 $f$ 数组，$f_i$ 表示在该区间内选出 $i$ 个数相乘所有方案之和。

则令 $ls$ 为左儿子，$rs$ 为右儿子，易得转移：

$$f_i=ls.f_i+rs.f_i\sum\limits^{c-1}_{i=1}ls.f_i\cdot rs.f_{c-j}$$

修改操作，如果是区间反转直接把 $i$ 为奇数的 $f_i$ 取个相反数，重点在于区间加。

先考虑计算 $\prod^k_{i=1}(a_i+x)-\prod^k_{i=1}a_i$。

观察 $\prod^k_{i=1}(a_i+x)$ 的展开式，得到上式等于 $\sum\limits^k_{i=1}x_i\cdot g_{k-i}$

$g_i$ 表示在 $a_1…a_k$ 中选出 $i$ 个数相乘的所有方案总和。

由于在一个线段树节点对应的区间中有很多长度为 $k$ 的区间，显然不能一一计算 $g$ 数组，由于 $f,g$ 定义非常相似，考虑利用 $f$ 推导 $g$。

其实可以得到，对于一个区间 $[l,r]$，$f_i=\sum\limits_{p_1,p_2..p_k\in [l,r]}\prod^k_{i=1}(a_{p_i}+x)-\prod^k_{i=1}a_{p_i}$。

也就是说，我们其实要计算：从 $[l,r]$ 区间中选出一个长度为 $k$ 的子序列，再从中选出一个长度为 $k-i$ 的子序列，计算这些子序列所有数的乘积之和。

假设 $[l,r]$ 区间长度为 $n$。

直接选出 $k-i$ 个数有 $\tbinom{n}{k-i}$ 种方案，按照上述方式选择有 $\tbinom{n}{k}\tbinom{k}{k-i}$ 种方案，即每种在区间 $[l,r]$ 直接选子序列的每种方案都被计算了 $\frac{\tbinom{n}{k}\tbinom{k}{k-i}}{\tbinom{n}{i}}=\tbinom{n-k+i}{i}$ 种方案。

那么最终答案就是，将区间 $[l,r]$ 加上一个数 $x$ 后，$f_k$ 会增加

$$\sum\limits^{i\le k}_{i=1}x_i\cdot \tbinom{n-k+i}{i}\cdot f_{k-i}$$

那么本题唯一的难点区间加操作就解决了。

区间查询按照最开始提到的转移搞一搞就行了，由于需要返回一个数组注意及时 delete 亿些空间防止内存泄漏（其实我没delete完，但足以应付这题的空间限制）。

最后注意懒标记，我pushdown时先考虑反转标记再考虑加法标记，那么每次一个节点收到反转标记时都要将它的加法标记取相反数。

出人意料的是这题虽然代码不短但很好写（

#include <cstdio>
#define int long long
inline int min(const int x, const int y) {return x < y ? x : y;}

const int mod = 19940417;
struct Node {
	int l, r, n, c[21], Lazy;
	bool rev;
} tree[200005];
typedef int* Array;
int a[50005], C[50005][21], n, q;

void pushup(int O) {
	for (int i = 1; i <= min(20, tree[O].n); ++ i) {
		tree[O].c[i] = tree[O << 1].c[i] + tree[O << 1 | 1].c[i];
		for (int j = 1; j < i; ++ j)
			tree[O].c[i] = (tree[O].c[i] + tree[O << 1].c[j] * tree[O << 1 | 1].c[i - j]) % mod;
	}
}
void reverse(int O) {
	for (int i = 1; i <= min(20, tree[O].n); i += 2)
		tree[O].c[i] = -tree[O].c[i];
	tree[O].Lazy = -tree[O].Lazy;
}
void add(int O, int d) {
	for (int i = min(20, tree[O].n); i; -- i) {
		int ret = 0;
		for (int j = 1, x = d; j <= i; ++ j, x = x * d % mod)
			ret = (ret + x * C[tree[O].n - i + j][j] % mod * tree[O].c[i - j]) % mod;
		tree[O].c[i] = (tree[O].c[i] + ret);
	}
}
void pushdown(int O) {
	if (tree[O].rev) {
		tree[O << 1].rev ^= 1, tree[O << 1 | 1].rev ^= 1;
		reverse(O << 1), reverse(O << 1 | 1);
		tree[O].rev = false;
	}
	if (tree[O].Lazy) {
		tree[O << 1].Lazy += tree[O].Lazy, tree[O << 1 | 1].Lazy += tree[O].Lazy;
		add(O << 1, tree[O].Lazy), add(O << 1 | 1, tree[O].Lazy);
		tree[O].Lazy = 0;
	}
}

void make_tree(int O, int L, int R) {
	tree[O].l = L, tree[O].r = R, tree[O].n = R - L + 1, tree[O].c[0] = 1;
	if (L != R) {
		make_tree(O << 1, L, L + R >> 1);
		make_tree(O << 1 | 1, (L + R >> 1) + 1, R);
		pushup(O);
	} else tree[O].c[1] = a[L];
}

void update(int O, int L, int R, int d) {
	if (L <= tree[O].l && tree[O].r <= R) {
		add(O, d), tree[O].Lazy += d; return;
	}
	int mid = tree[O].l + tree[O].r >> 1;
	pushdown(O);
	if (L <= mid) update(O << 1, L, R, d);
	if (mid < R) update(O << 1 | 1, L, R, d);
	pushup(O);
}
void Reverse(int O, int L, int R) {
	if (L <= tree[O].l && tree[O].r <= R) {
		reverse(O), tree[O].rev ^= 1; return;
	}
	int mid = tree[O].l + tree[O].r >> 1;
	pushdown(O);
	if (L <= mid) Reverse(O << 1, L, R);
	if (mid < R) Reverse(O << 1 | 1, L, R);
	pushup(O);
}
Array query(int O, int L, int R) {
	if (L <= tree[O].l && tree[O].r <= R) {
		int* c = new int[21];
		for (int i = 0; i <= 20; ++ i) c[i] = 0;
		for (int i = 1; i <= min(20, tree[O].n); ++ i) c[i] = tree[O].c[i];
		return c;
	}
	pushdown(O);
	int mid = tree[O].l + tree[O].r >> 1;
	if (mid >= R) return query(O << 1, L, R);
	if (L > mid) return query(O << 1 | 1, L, R);
	int *a = query(O << 1, L, R), *b = query(O << 1 | 1, L, R), *c = new int[21];
	for (int i = 0; i <= 20; ++ i) c[i] = 0;
	for (int i = 1; i <= min(20, tree[O].n); ++ i) {
		c[i] = a[i] + b[i];
		for (int j = 1; j < i; ++ j) c[i] = (c[i] + a[j] * b[i - j] % mod) % mod;
	}
	delete a, delete b;
	return c;
}

signed main() {
	scanf("%lld%lld", &n, &q);
	C[0][0] = 1;
	for (int i = 1; i <= n; ++ i) {
		scanf("%lld", a + i);
		C[i][0] = 1;
		for (int j = 1; j <= min(i, 20); ++ j)
			C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
	}
	make_tree(1, 1, n);
	while (q --) {
		char opt;
		int l, r, v;
		scanf(" %c%lld%lld", &opt, &l, &r);
		if (opt == 'I') scanf("%lld", &v), update(1, l, r, v);
		else if (opt == 'R') Reverse(1, l, r);
		else scanf("%lld", &v), printf("%lld\n", (query(1, l, r)[v] + mod) % mod);
	}
}