记答案为 ，则考虑套路的对 条件容斥，钦定有 个位置 满足 且 ，剩下的数随便放，答案可以被表示为：
需要特判 的情况，此时答案显然为 。
套路的考虑离线所有询问然后用莫队来维护这个东西，问题在于如何快速的求出 后的变化量 。
直接对着 的式子做差看着就很难搞，考虑先把 改写成更简单的形式：
这个东西还是很难维护，但 已经没法继续化简了，想要进一步直接对着这个搞事情的话可以把 写成生成函数的形式 ，但是看上去这个也没啥好的性质搞下去。
考虑换一个方向思考，先对式子换元，记 ，则 。把式子的后半部分拿出来即 ，则得到 后就有 。
考虑对 快速求出 两个量 后的变化量 。此时考虑同时维护 两个值，这样在 两个量 时就可以 做到两个量互相转移，具体过程这里不再赘述。
因此直接拿普通莫队维护即可，时间复杂度为 。
:::success[代码]
namespace lowspeed_song {
int fac[N], inv[N], ifac[N];
inline void init() {
fac[0] = inv[0] = ifac[0] = 1;
fac[1] = inv[1] = ifac[1] = 1;
for (int i = 2; i < N; ++i) {
fac[i] = fac[i - 1] * i % mod;
inv[i] = mod - inv[mod % i] * (mod / i) % mod;
ifac[i] = ifac[i - 1] * inv[i] % mod;
}
}
inline int binom(int a, int b) {
if (b < 0 || a < b) return 0;
return fac[a] * ifac[b] % mod * ifac[a - b] % mod;
}
int res[N];
struct Query { int r, m, id; } Q[N];
inline void addM(int &R, int &M, int &x, int &y) {
int tmp = ((R + M + 1) * x + R * y % mod) % mod;
if (R > 0) y = (x + y) % mod;
else y = 0;
x = tmp, ++M;
}
inline void delM(int &R, int &M, int &x, int &y) {
int tmp = (x - R * y % mod + mod) * inv[M] % mod;
if (R > 0) y = (y + mod - tmp) % mod;
else y = 0;
x = tmp, --M;
}
inline void addR(int &R, int &M, int &x, int &y) {
int tmp = ((R + M) * x % mod + R * y % mod) % mod;
y = x, x = tmp, ++R;
}
inline void delR(int &R, int &M, int &x, int &y) {
if (R == 1) x = y, y = 0;
else {
int tmp = (x - y * (R + M - 1) % mod + mod) % mod * inv[R - 1] % mod;
x = y, y = tmp;
} --R;
}
inline void sol() {
int q; cin >> q;
for (int i = 0; i < q; ++i) {
int n, m; cin >> n >> m;
if (m < 0 || n < m * 2) { res[i] = -1; continue; }
Q[i] = {n - m - m, m, i};
}
int B = 316;
sort(Q, Q + q, [&](auto &l, auto &r) {
return l.r / B < r.r / B || l.r / B == r.r / B && l.m < r.m;
});
int R = 0, M = 0, x = 1, y = 0;
for (int i = 0; i < q; ++i) {
while (R < Q[i].r) addR(R, M, x, y);
while (R > Q[i].r) delR(R, M, x, y);
while (M < Q[i].m) addM(R, M, x, y);
while (M > Q[i].m) delM(R, M, x, y);
if (~res[Q[i].id]) res[Q[i].id] = fac[Q[i].r + Q[i].m] * ifac[Q[i].r] % mod * x % mod;
else res[Q[i].id] = 0;
}
for (int i = 0; i < q; ++i) cout << res[i] << '\n';
}
} // namespace lowspeed_song:::
喜欢的话，留下你的评论吧～