P4247

全部WA

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 19940417;

template <typename T>
inline void read(T &ans)
{
	char ch = getchar();
	int f = 1;
	ans = 0;
	for (; !isdigit(ch); ch = getchar())
		ch == '-' ? f = -1 : f = 1;
	for (; isdigit(ch); ch = getchar())
		ans = (ans << 3) + (ans << 1) + (ch & 15);
	ans *= f;
	return;
}
template <typename T, typename... Args>
inline void read(T &tmp, Args &...tmps)
{
	read(tmp);
	read(tmps...);
}

template <class T>
inline void print(T ret, int flg = 0)
{
	static int sta[35];
	T x = ret;
	int top = 0;
	bool f = (ret < 0);
	if (ret < 0)
		x = -x;
	do
	{
		sta[top++] = x % 10, x /= 10;
	} while (x);
	if (f)
		putchar('-');
	while (top)
		putchar(sta[--top] + 48);
	if (flg == 0)
		putchar(' ');
	else if (flg == 1)
		putchar('\n');
}

int C[50010][21], a[50010];
int n, m;

struct tree
{
	int size;
	int c[21];
	int add;
	int f;
} t[50010 << 2];


inline void pushup(int rt)
{
	memset(t[rt].c, 0, sizeof(t[rt].c));
	for (int i = 0; i <= t[rt << 1].size && i <= 20; ++i)
		for (int j = 0; i + j <= 20 && j <= t[rt << 1 | 1].size; ++j)
			t[rt].c[i + j] = (t[rt].c[i + j] + t[rt << 1].c[i] * t[rt << 1 | 1].c[j] % MOD) % MOD;
}


inline void build(int rt, int l, int r)
{
	t[rt].size = r - l + 1;
	if (l == r)
	{
		t[rt].c[0] = 1;
		t[rt].c[1] = (a[l] % MOD + MOD) % MOD;
		return;
	}
	int mid = (l + r) >> 1;
	build(rt << 1, l, mid);
	build(rt << 1 | 1, mid + 1, r);
	pushup(rt);
}


inline void puad(int q, int x)
{
	if (!q || !x)
		return;
	int tmp[50];
	tmp[0] = 1;
	for (int i = 1; i <= 20 && i <= t[q].size; i++)
		tmp[i] = tmp[i - 1] * x % MOD;
	for (int i = min((int)20, t[q].size); i != 0; i--)
		for (int j = 0; j < i; j++)
			t[q].c[i] = (t[q].c[i] + t[q].c[j] * tmp[i - j] % MOD * C[t[q].size - j][i - j]) % MOD;
	t[q].add = (t[q].add + x) % MOD;
}


inline void pure(int q)
{
	if (!q)
		return;
	for (int i = 1; i <= 20 && i <= t[q].size; i++)
	{
		if (i % 2)
			t[q].c[i] = MOD - t[q].c[i];
		else
			continue;
	}
	t[q].f ^= 1;
	t[q].add = MOD - t[q].add;
}

inline tree change(tree a, tree b)
{
	tree res;
	res.size = a.size + b.size;
	memset(res.c, 0, sizeof(res.c));
	for (int i = 0; i <= (int)20 && i <= a.size; ++i)
		for (int j = 0; j + i <= (int)20 && j <= b.size; ++j)
			res.c[i + j] = (res.c[i + j] + a.c[i] * b.c[j] % MOD) % MOD;
	return res;
}

inline void pushdown(int rt)
{
	if (t[rt].f)
	{
		pure(rt << 1);
		pure(rt << 1 | 1);
		t[rt].f = 0;
	}
	if (t[rt].add)
	{
		puad(rt << 1, t[rt].add);
		puad(rt << 1 | 1, t[rt].add);
		t[rt].add = 0;
	}
}

inline void upd(int rt, int l, int r, int ql, int qr, int v)
{
	if (l > qr || r < ql)
		return;
	if (l >= ql && r <= qr)
	{
		puad(rt, v);
		return;
	}
	pushdown(rt);
	int mid = (l + r) >> 1;
	upd(rt << 1, l, mid, ql, qr, v);
	upd(rt << 1 | 1, mid + 1, r, ql, qr, v);
	pushup(rt);
}

inline tree qry(int rt, int l, int r, int ql, int qr)
{
	if (l >= ql && r <= qr)
		return t[rt];
	pushdown(rt);
	int mid = (l + r) >> 1;
	if (qr <= mid)
		return qry(rt << 1, l, mid, ql, qr);
	else if (ql > mid)
		return qry(rt << 1 | 1, mid + 1, r, ql, qr);
	else
		return change(qry(rt << 1, l, mid, ql, qr), qry(rt << 1 | 1, mid + 1, r, ql, qr));
}

inline void rev(int rt, int l, int r, int ql, int qr)
{
	if (l > qr || r < ql)
		return;
	if (l >= ql && r <= qr)
	{
		pure(rt);
		return;
	}
	pushdown(rt);
	int mid = (l + r) >> 1;
	rev(rt << 1, l, mid, ql, qr);
	rev(rt << 1 | 1, mid + 1, r, ql, qr);
	pushup(rt);
}

inline void init()
{
	t[0].c[0] = 1;
	for (int i = 1; i <= n; ++i)
	{
		C[i][0] = 1;
		for (int j = 1; j <= i && j <= 20; ++j)
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
	}
}

signed main()
{
	read(n, m);
	C[0][0] = 1;
	init();
	for (int i = 1; i <= n; ++i)
		read(a[i]);
	build(1, 1, n);
	for (int i = 1; i <= m; ++i)
	{
		char op = getchar();
		while (op ^ 'I' && op ^ 'R' && op ^ 'Q')
			op = getchar();
		if (op == 'I')
		{
			int a, b, c;
			read(a, b, c);
			upd(1, 1, n, a, b, c);
		}
		else if (op == 'R')
		{
			int a, b;
			read(a, b);
			rev(1, 1, n, a, b);
		}
		else
		{
			int a, b, c;
			read(a, b, c);
			tree res = qry(1, 1, n, a, b);
			if (res.c[c] < 0)
				print((MOD - res.c[c]));
			else
				print(res.c[c] % MOD);
			putchar('\n');
		}
	}
	return 0;
}