上一篇杂题里，新的题目严重阻碍了老题目的生长。为了解除顶端抑制，一部分伸长区被移植到这里了。
A - Range Set
https://www.luogu.com.cn/problem/AT_agc045_c
首先考虑 \(A\le B\) 的情况。覆盖类问题的一个想法是倒推回
?（这种方法的优点在于，操作总能和原始操作一一对应，形成和正向操作序列的双射，通过倒推得到的性质总是充要的）。则目标串为长度为 \(n\) 的
0?串，起始串为待判定串，可进行的操作有：选择一个长度为 \(B\) 的
1?串，全部变为?；选择一个长度为 \(A\) 的
0?串，全部变为?。
容易发现，只要在任意时刻进行了一次 1 操作，总能通过若干次 1 2 操作扩展到一个长为 \(n\) 的
0?序列（而一次 1 操作都不做只有一种情况，虽然在后面 DP 会自然统计到这种情况）。故目标转化为找到能够进行第一次（又一个经典技巧）1 操作的局面。容易发现当且仅当能够通过若干次 2 操作，得到一个长度 \(\ge B\) 的
1?串，显然的等价转换是，存在一个长度 \(\ge B\) 的子串，里面所有0的连续段长度均 \(\ge A\)。现在就可以想办法统计了。接下来考虑 \(B<A\) 的情况，容易发现，只要在任意时刻进行了一次 2 操作，总能通过若干次 1 2 操作扩展到一个长为 \(n\) 的
0?序列。把上面得到所有合法串 flip 就可以得到这里的所有合法串，故并不需要分讨。令 \(f_{i,j,0/1}\) 表示 DP 到 \(i\)，有一段长度为 \(j\) 的合法后缀，第 \(i-1\) 位的值为 \(0/1\) 的方案数，则：
\[ f_{i,j,1}=\sum_{k=1}^j f_{i-k,j-k,0}\\ f_{i,j,0}=\left(\sum_{k=1}^{\min(A-1,j-B)}f_{i-k,j-k,1}\right)+\left(\sum_{k=A}^j f_{i-k,j-k,1}\right)\\ f_{i,0,0}=\sum_{k=1}^{A-1}\sum_{j=0}^{B-1} f_{i-k,j,1} \]
最后一种转移的优化是显然的；前两种转移中，\(i\) 和 \(j\) 的变化量是一致的，也可以前缀和优化。
#include <bits/stdc++.h>
const int mod = 1e9 + 7;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n, a, b;
std::cin >> n >> a >> b;
if (a > b)
std::swap(a, b);
using arr = std::vector<long long>;
using brr = std::vector<arr>;
using crr = std::vector<brr>;
brr sum(n + 1, arr(n + 1));
crr s(2, brr(n + 1, arr(n + 1)));
sum[0][0] = 1ll;
s[0][0][0] = s[1][0][0] = 1ll;
auto fun = [&](int op, int i, int j, int l, int r) {
if (l > r)
return 0ll;
auto res = s[op][i - j][i - l];
if (i > r)
res += mod - s[op][i - j][i - r - 1];
return res < mod ? res : res - mod;
};
auto res = 0ll;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n && j <= i; ++j) {
auto f0 = fun(1, i, j, 1, std::min(a - 1, j - b)) + fun(1, i, j, a, j);
auto f1 = fun(0, i, j, 1, j);
if (f0 >= mod)
f0 -= mod;
if ((s[0][i - j][i] = s[0][i - j][i - 1] + f0) >= mod)
s[0][i - j][i] -= mod;
if ((s[1][i - j][i] = s[1][i - j][i - 1] + f1) >= mod)
s[1][i - j][i] -= mod;
if (i == n && j >= b)
res += f0 + f1;
if ((sum[i][j] = sum[i][j - 1] + f1) >= mod)
sum[i][j] -= mod;
}
s[0][i][i] = 0ll;
for (int k = 1; k < a && k <= i; ++k)
s[0][i][i] += sum[i - k][std::min(b - 1, i - k)];
s[0][i][i] %= mod;
}
std::cout << res % mod << '\n';
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}B - Popping Balls
https://www.luogu.com.cn/problem/AT_code_festival_2017_qualb_e
容易发现好的出发点应该是尽可能多地统计局面。容易发现应该尽量让 \(s\) 和 \(t\) 取到蓝色的球。
进一步发现，在第一次取蓝球时，\(t\) 应该在蓝球的队首处。直到取走了 \(B\) 个球，\(t\) 已经超出序列时，\(s\) 才可能发挥作用。
相似地，在这之后第一次取蓝球时，\(s\) 应该在蓝球的队首处。
很容易发现只需要统计两个点处分别取走了多少个蓝球（尽量让 \(t\) 取）就能统计。
具体地，设 \(t\) 处取走了 \(c\) 个、\(s\) 处取走了 \(d\) 个，则这两个点处的方案数为：
\[ \binom{B-1}{c-1}\times \binom{B-c-1}{d-1} \]
此外，总共 \(A-(B-c)-(B-c-d)\) 个红球，可以在 \(t\) 进入决策之前，\(s\) 进入决策之前，\(s\) 决策完后三个时刻给出去。插板得到 \(\binom{A-(B-c)-(B-c-d)+2}2\) 种方案。
此外，还要考虑 \(s\) 与 \(t\) 重合，共 \(A+1\) 种方案。
#include <bits/stdc++.h>
const int mod = 1e9 + 7;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int A, B;
std::cin >> A >> B;
using arr = std::vector<long long>;
using brr = std::vector<arr>;
brr C(A + B + 1, arr(A + B + 1));
C[0][0] = 1ll;
for (int i = 1; i <= A + B; ++i) {
C[i][0] = 1ll;
for (int j = 1; j <= i; ++j)
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
}
auto res = A + 1;
for (int c = 1; c < B; ++c)
for (int d = 1; c + d <= B; ++d)
(res += C[B - 1][c - 1] * C[B - c - 1][d - 1] % mod * C[std::max(0, A - (B - c) - (B - c - d) + 2)][2] % mod) %= mod;
std::cout << res << '\n';
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}C - Minimum Bounding Box 2
https://www.luogu.com.cn/problem/AT_abc297_f
- 枚举矩形长宽，二项式算方案数即可，非常简单。
#include <bits/stdc++.h>
const int mod = 998244353;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n, m, k;
std::cin >> n >> m >> k;
using arr = std::vector<long long>;
using brr = std::vector<arr>;
arr fac(n * m + 1), inv(n * m + 1);
fac[0] = inv[0] = 1ll;
for (int i = 1; i <= n * m; ++i)
fac[i] = fac[i - 1] * i % mod;
auto qkp = [&](long long x, int y) {
auto res = 1ll;
for (; y; (x *= x) %= mod, y >>= 1)
if (y & 1)
(res *= x) %= mod;
return res;
};
inv[n * m] = qkp(fac[n * m], mod - 2);
for (int i = n * m - 1; i; --i)
inv[i] = inv[i + 1] * (i + 1) % mod;
auto C = [&](int n, int m) {
if (n < m)
return 0ll;
return fac[n] * inv[m] % mod * inv[n - m] % mod;
};
auto res = 0ll;
brr f(n + 1, arr(m + 1)), g(n + 1, arr(m + 1));
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
g[i][j] = C(i * j, k);
f[i][j] = g[i][j] - g[i - 1][j] * 2 - g[i][j - 1] * 2 + g[i - 1][j - 1] * 4;
if (i >= 2)
f[i][j] += g[i - 2][j] - 2 * g[i - 2][j - 1];
if (j >= 2)
f[i][j] += g[i][j - 2] - 2 * g[i - 1][j - 2];
if (i >= 2 && j >= 2)
f[i][j] += g[i - 2][j - 2];
f[i][j] = (f[i][j] % mod + mod) % mod;
(res += i * j * f[i][j] % mod * (n - i + 1) % mod * (m - j + 1)) %= mod;
// printf("f[%d][%d] = %lld \n", i, j, f[i][j]);
}
std::cout << res * qkp(C(n * m, k), mod - 2) % mod << '\n';
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}D - Colorful Candies 2
https://www.luogu.com.cn/problem/AT_abc215_g
啥啊。原来要拆贡献。
观察到类根号的复杂度，考虑把出现次数相同的数放在一起计算，元素种类就只有 \(O(\sqrt n)\) 个了。
DP 不太能处理这样的多重结构，故需要考虑更线性的计算方式，这里进行了拆贡献。
考虑一个出现了 \(c\) 次的数被选入的概率，为 \(1-\dfrac {C_{n-c}^K}{C_{n}^K}\)。相加即可。
#include <bits/stdc++.h>
const int mod = 998244353;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n;
std::cin >> n;
std::unordered_map<int, int> cnt;
for (int i = 1, x; i <= n; ++i)
std::cin >> x, ++cnt[x];
std::vector<int> b;
for (auto [x, y] : cnt)
b.push_back(y);
std::sort(b.begin(), b.end());
std::vector<std::pair<int, int> > a;
std::vector<long long> fac(n + 1), inv(n + 1);
fac[0] = inv[0] = 1ll;
for (int i = 1; i <= n; ++i)
fac[i] = fac[i - 1] * i % mod;
auto qkp = [&](long long x, int y) {
auto res = 1ll;
for (; y; (x *= x) %= mod, y >>= 1)
if (y & 1)
(res *= x) %= mod;
return res;
};
inv[n] = qkp(fac[n], mod - 2);
for (int i = n - 1; i; --i)
inv[i] = inv[i + 1] * (i + 1) % mod;
for (auto i : b)
if (a.empty() || i != a.back().first)
a.emplace_back(i, 1);
else
++a.back().second;
auto C = [&](int n, int m) {
if (n < m)
return 0ll;
return fac[n] * inv[m] % mod * inv[n - m] % mod;
};
for (int k = 1; k <= n; ++k) {
auto res = 0ll;
auto invC = qkp(C(n, k), mod - 2);
for (auto [c, m] : a)
res += m * (1ll + mod - C(n - c, k) * invC % mod);
std::cout << res % mod << '\n';
}
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}A - Catastrophic Roulette
https://www.luogu.com.cn/problem/AT_arc174_c
B - Swap Permutation
https://www.luogu.com.cn/problem/AT_arc176_d
发现最后关心的位置比较少，只有 \(O(n)\) 个。同时发现一件事：假设 \(A_i=x,A_{i+1}=y\)，那么最后 \(A_i\) 和 \(A_{i+1}\) 的值的可能情况只有：
\((x,y)\)，\((x,?)\)，\((y,x)\)，\((y,?)\)，\((?,x)\)，\((?,y)\)，\((?,?)\)
这 7 种情况。且每种情况的期望是相对好算的。发现每种情况出现的概率可以用矩阵求解。
发现矩阵有点大。题解区中的处理方法之一是经典的偏序 + 01，但为什么不能沿用原本的思路呢？
进一步把 \(A,B\) 视作同一个数，这样状态数就减少到 3 种 \((0,0),(0,1)/(1,0),(1,1)\)，相应的期望也是好算的，且矩阵大小会减少很多。
\[ M=\begin{bmatrix} \dfrac {(n-2)(n-3)}2+1+2(n-4)&2\times 2&0\\ n-3&2+(n-3)+\dfrac {(n-2)(n-3)}2&1\\ 0&(n-2)\times 2&1+\dfrac {(n-2)(n-3)}2 \end{bmatrix} \]
检查技巧：保证每一行的和均为 \(\dfrac {n(n-1)}2\) 即可。
#include <bits/stdc++.h>
const int mod = 998244353, inv2 = (mod + 1) >> 1, N = 3;
struct mat {
std::vector<std::vector<long long> > a;
mat(void): a(N, std::vector<long long> (N)) {}
std::vector<long long>& operator[](const int q) {
return a[q];
}
mat operator* (mat &q) const {
mat res;
for (int i = 0; i < N; ++i)
for (int k = 0; k < N; ++k)
for (int j = 0; j < N; ++j)
if ((res[i][j] += a[i][k] * q[k][j] % mod) >= mod)
res[i][j] -= mod;
return res;
}
};
struct vec {
std::vector<long long> a;
vec(void): a(N) {}
long long& operator[](const int q) {
return a[q];
}
vec operator* (mat &q) const {
vec res;
for (int k = 0; k < N; ++k)
for (int j = 0; j < N; ++j)
if ((res[j] += a[k] * q[k][j] % mod) >= mod)
res[j] -= mod;
return res;
}
};
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
long long n, m;
std::cin >> n >> m;
std::vector<long long> a(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
if (n == 2) {
std::cout << std::abs(a[1] - a[2]) << '\n';
return 0;
}
auto qkp = [&](long long x, int y) {
auto res = 1ll;
for (; y; (x *= x) %= mod, y >>= 1)
if (y & 1)
(res *= x) %= mod;
return res;
};
vec d;
d[2] = 1ll;
mat t;
t[0][0] = ((n - 2) * (n - 3) / 2 + 1 + 2 * (n - 4)) % mod;
t[0][1] = 2 * 2;
t[1][0] = n - 3;
t[1][1] = (2 + (n - 3) + (n - 2) * (n - 3) / 2) % mod;
t[1][2] = 1;
t[2][1] = (n - 2) * 2 % mod;
t[2][2] = (1 + (n - 2) * (n - 3) / 2) % mod;
for (int i = m; i; i >>= 1, t = t * t)
if (i & 1)
d = d * t;
auto s = 0ll;
auto calc = [&](long long l, long long r) {
return (l + r) * (r - l + 1) / 2 % mod;
};
for (int i = 1; i <= n; ++i)
s += (calc(i + 1, n) + mod - (long long)i * (n - (i + 1) + 1) % mod) % mod;
auto res = 0ll, invM = qkp((long long)(n - 2) * (n - 3) / 2 % mod, mod - 2), invN2 = qkp(n - 2, mod - 2);
for (int i = 1; i < n; ++i) {
auto k = (calc(a[i] + 1, n) - a[i] * (n - (a[i] + 1) + 1) % mod + a[i] * (a[i] - 1) % mod - calc(1, a[i] - 1) - std::abs(a[i] - a[i + 1]) + calc(a[i + 1] + 1, n) - a[i + 1] * (n - (a[i + 1] + 1) + 1) % mod + a[i + 1] * (a[i + 1] - 1) % mod - calc(1, a[i + 1] - 1) - std::abs(a[i] - a[i + 1])) % mod, t = (s - k - std::abs(a[i] - a[i + 1])) % mod;
res += t * invM % mod * d[0] % mod;
res += d[1] % mod * invN2 % mod * inv2 % mod % mod * k % mod;
res += std::abs(a[i] - a[i + 1]) * d[2] % mod;
}
std::cout << (res % mod + mod) % mod << '\n';
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}C - Random Walk on Tree
https://www.luogu.com.cn/problem/AT_arc185_d
- 即一个根上挂了 \(n\div m\) 条长为 \(m\) 的链。令 \(f_i\) 表示走到一条链底
