P4247 [清华集训2012]序列操作
Solution
观察数据范围，发现 \(c\le 20\)，提示我们此题可能有与 \(c\) 相关的复杂度的解法。
这道题的中心就在第三个操作，我们不妨先思考静态询问怎么做。
记 \(f[l][r][i]\) 表示 \([l,r]\) 内选 \(i\) 个数相乘的所有方案的和，则：
\[f[l][r][i] = \sum\limits_{k = 0}^{i}f[l][j][k]\times f[j + 1][r][i - k] \]其中 \(j\) 可以为 任意 \([l, r]\) 内的位置。
既然如此，我们不妨令 \(j = mid\)，这不就很线段树了吗？
然后再考虑修改。
举一个最简单的例子 \(a_{1}a_{2} + a_{2}a_{3} + a_{1}a_{3} \to (a_{1} + val)(a_{2} + val) + (a_{2} + val)(a_{3} + val) + (a_{1} + val)(a_{3} + val)\) 来观察。
记新数列的答案为 \(f^{'}[l][r][i]\)，考虑如何用 \(f\) 更新 \(f^{'}\)。
发现新式可以视为一个关于 \(val\) 的 \(c\) 次多项式，我们不妨枚举 \(val\) 的次数，发现刚好可以凑出 \(f\)，即：
\[f^{'}[l][r][i] = \sum\limits_{k = 0}^{i}\left( \binom{len - i + k}{k}f[l][r][i - k] \right) val^{k} \]这里 \(len = r - l + 1\)。
对于组合系数，可以理解为：
乘积项共 \(\binom{len}{i}\) 组，每组中的 \(val^{k}\) 项可由 \(\binom{i}{k}\) 个 \(\left( \prod\limits_{j = 1}^{i - k} a_{b_j} \right)val^{k}\) 的形式累加起来，而 \(f[l][r][i - k]\) 中已经蕴含了 \(\binom{len}{i - k}\) 种选法，所以系数应为
\[\frac{\binom{len}{i}\binom{i}{k}}{\binom{len}{i - k}} = \binom{len - i + k}{k}. \]对于正负反转的操作，其实就是：
\[f^{'}[l][r][i] = f[l][r][i], i \equiv 1 \pmod{2} \]注意先处理正负标记再处理加标记。
#include<bits/stdc++.h>
#define LL long long
#define MOD 19940417
#define ls(x) x << 1
#define rs(x) x << 1 | 1
using namespace std;
int inc(const int &a, const int &b)
{
return a + b >= MOD ? a + b - MOD : a + b;
}
int dec(const int &a, const int &b)
{
return a - b < 0 ? a - b + MOD : a - b;
}
int mul(const int &a, const int &b)
{
return 1LL * a * b % MOD;
}
int adt(const int &a)
{
return (a % MOD + MOD) % MOD;
}
void Inc(int &a, const int &b)
{
((a += b) >= MOD) && (a -= MOD);
}
void Mul(int &a, const int &b)
{
a = 1LL * a * b % MOD;
}
const int N = 5e4 + 5;
int n, Q, a[N];
int C[N][21];
void preprocess()
{
C[0][0] = 1;
for(int i = 1; i < N; ++i)
for(int j = 0; j <= min(i, 20); ++j)
{
if(!j) C[i][j] = 1;
else C[i][j] = inc(C[i - 1][j], C[i - 1][j - 1]);
}
}
struct Nagisa
{
int rev, add;
};
struct SegTree
{
int l, r;
int f[21];
Nagisa dango;
};
struct SGT
{
SegTree tr[4 * N];
void pushup(SegTree &u, SegTree L, SegTree R)
{
for(int i = 0; i <= 20; ++i)
{
u.f[i] = 0;
for(int k = 0; k <= i; ++k)
Inc(u.f[i], mul(L.f[k], R.f[i - k]));
}
}
void build(int p, int l, int r)
{
tr[p].l = l;
tr[p].r = r;
tr[p].f[0] = 1;
tr[p].dango.rev = 1;
tr[p].dango.add = 0;
if(l == r)
{
tr[p].f[1] = adt(a[l]);
return;
}
int mid = l + (r - l) / 2;
build(ls(p), l, mid);
build(rs(p), mid + 1, r);
pushup(tr[p], tr[ls(p)], tr[rs(p)]);
}
void cal_rev(SegTree &u, int rev)
{
if(rev == 1) return;
int lim = min(u.r - u.l + 1, 20);
for(int i = 1; i <= lim; i += 2)
u.f[i] = dec(MOD, u.f[i]);
u.dango.add = dec(MOD, u.dango.add);
u.dango.rev = -u.dango.rev;
}
void cal_add(SegTree &u, int add)
{
if(add == 0) return;
add = adt(add);
int len = u.r - u.l + 1;
int lim = min(len, 20);
for(int i = lim; i >= 1; --i)
for(int k = 1, w = add; k <= i; ++k, Mul(w, add))
Inc(u.f[i], mul(mul(w, C[len - i + k][k]), u.f[i - k]));
Inc(u.dango.add, add);
}
void cal(SegTree &u, Nagisa dango)
{
cal_rev(u, dango.rev);
cal_add(u, dango.add);
}
void pushdown(int p)
{
if(tr[p].dango.rev == -1 || tr[p].dango.add)
{
cal(tr[ls(p)], tr[p].dango);
cal(tr[rs(p)], tr[p].dango);
tr[p].dango.add = 0;
tr[p].dango.rev = 1;
}
}
void modify(int p, int l, int r, Nagisa dango)
{
if(tr[p].l >= l && tr[p].r <= r)
{
cal(tr[p], dango);
return;
}
pushdown(p);
int mid = tr[p].l + (tr[p].r - tr[p].l) / 2;
if(mid >= l) modify(ls(p), l, r, dango);
if(mid < r) modify(rs(p), l, r, dango);
pushup(tr[p], tr[ls(p)], tr[rs(p)]);
}
SegTree query(int p, int l, int r)
{
if(tr[p].l >= l && tr[p].r <= r)
return tr[p];
pushdown(p);
int mid = tr[p].l + (tr[p].r - tr[p].l) / 2;
if(mid < l) return query(rs(p), l, r);
else if(mid >= r) return query(ls(p), l, r);
else
{
SegTree L = query(ls(p), l, r);
SegTree R = query(rs(p), l, r);
SegTree res;
pushup(res, L, R);
return res;
}
}
}tr;
int main()
{
preprocess();
scanf("%d %d", &n, &Q);
for(int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
tr.build(1, 1, n);
while(Q--)
{
char op;
scanf(" %c", &op);
if(op == 'I')
{
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
tr.modify(1, a, b, (Nagisa){1, c});
}
if(op == 'R')
{
int a, b;
scanf("%d %d", &a, &b);
tr.modify(1, a, b, (Nagisa){-1, 0});
}
if(op == 'Q')
{
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
SegTree res = tr.query(1, a, b);
printf("%d\n", res.f[c]);
}
}
return 0;
}