数数，但是性质题
A - Reversi 2
https://www.luogu.com.cn/problem/AT_arc189_a
操作可以看成，任选一个点，找到两侧最近的颜色相异的点，进行推平。
或，任选一个极长连续段，推平为其两端的颜色。
很容易注意到最终序列被分为若干个极长连续段，彼此独立。对于起始序列，容易发现任意区间中的任意操作会减少 2 的不同段数量（故显然最终序列连续段长度应该为奇数，且两端颜色和目标颜色一致）。
令 \(f_i\) 为长度为 \(i\) 的连续段被推平的方案数（\(i\bmod2=1\)），那么有 \(f_i=(i - 2)\times f_{i-2}\)。
最终方案数应为所有极长段方案的多重集排列乘上它们各自独立方案数之积。
#include <bits/stdc++.h>
const int mod = 998244353;
int main() {
#ifdef ONLINE_JUDGE
std::ios::syns_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::vector<int> a(n + 1);
std::vector<long long> f(n + 1), fac(n + 1), inv(n + 1);
fac[0] = inv[0] = 1ll;
for (int i = 1; i <= n; ++i) {
std::cin >> a[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;
f[1] = 1;
for (int i = 3; i <= n; i += 2)
f[i] = f[i - 2] * (i - 2) % mod;
auto res = 1ll;
int L = 1, cnt = 0;
for (int i = 1; i <= n; ++i)
if (i == n || a[i + 1] != a[i]) {
if (a[i] != i % 2 || (i - L + 1) % 2 == 0) {
std::cout << 0 << '\n';
return 0;
}
(res *= f[i - L + 1]) %= mod;
(res *= inv[(i - L) / 2]) %= mod;
cnt += (i - L) / 2;
L = i + 1;
}
std::cout << res * fac[cnt] % 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 - Cigar Box
https://www.luogu.com.cn/problem/AT_arc112_e
发现一个数的状态只取决于，最后一次以它为主体的操作，及这次操作之后的所有操作
进一步地发现，按最后一次操作分类，可以分为，向左（
L）、向右（R）、没被操作过（M）三种类型。可以很显然地注意到，最终序列一定是
LLLMMMRRR的形式，其中，仅要求M是递增的；现在需要计算有多少长度为 \(m\) 的操作序列对应所有的LMR序列（如果认为所有的M始终是不动的可能会更好理解）。发现同种类数间，『最后一次操作』的相对顺序是固定的。进一步会发现这其实是第二类斯特林数，最后答案为：
\[ \sum_{L,R}\binom{L+R}{L}\cdot \begin{Bmatrix}m\\ L+R\end{Bmatrix}\cdot 2^{m-L-R} \]
#include <bits/stdc++.h>
const int mod = 998244353;
int main() {
#ifdef ONLINE_JUDGE
std::ios::syns_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;
std::cin >> n >> m;
using arr = std::vector<long long>;
arr pw(m + 1), fac(m + 1), inv(m + 1);
std::vector<arr> f(m + 1, arr(m + 1));
std::vector<int> a(n + 1);
std::vector<std::vector<int> > ok(n + 1, std::vector<int> (n + 1));
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
for (int l = 1; l <= n; ++l)
for (int r = l; r <= n; ++r)
if (r == l || a[r] > a[r - 1])
ok[l][r] = 1;
else
break;
f[1][1] = 1ll, pw[0] = fac[0] = inv[0] = 1ll;
for (int i = 2; i <= m; ++i)
for (int j = 1; j <= i; ++j)
f[i][j] = (f[i - 1][j - 1] + f[i - 1][j] * j) % mod;
for (int i = 1; i <= m; ++i) {
pw[i] = pw[i - 1] * 2 % mod;
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[m] = qkp(fac[m], mod - 2);
for (int i = m - 1; i; --i)
inv[i] = inv[i + 1] * (i + 1) % mod;
auto C = [&](int n, int m) {
return fac[n] * inv[m] % mod * inv[n - m] % mod;
};
auto res = 0ll;
for (int L = 0; L <= m && L <= n; ++L)
for (int R = 0; L + R <= m && L + R <= n; ++R)
if (L + 1 > n - R || ok[L + 1][n - R])
res += C(L + R, L) * f[m][L + R] % mod * pw[m - L - R] % 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;
}C - Swap Characters
https://www.luogu.com.cn/problem/AT_arc168_c
考虑值域为 \(0\) 和 \(1\) 的情况
发现这个很唐
好险，AI 差点比我先做出来了，转化成枚举操作次数 \(i\)，答案是\[ \sum_{i\le\min(s_0,s_1)}\binom{s_0}{i}\cdot\binom{s_1}{i} \]
根据这个可以得到启发，发现所谓任意交换可以转化为，每个字母的支出和收入相等，故考虑画个表：
A - LEQ and NEQ / Non-equal Neighbours
https://www.luogu.com.cn/problem/AT_arc115_e / https://www.luogu.com.cn/problem/CF1591F / https://www.luogu.com.cn/problem/CF1585F
容斥，钦定有 \(i\) 对相同元素，那么答案为 \(\sum\limits_{i=0}^{n-1} (-1)^{n-1-i} \cdot g_i\)，其中 \(g_i\) 表示至少有 \(i\) 对相同元素的方案数。
考虑 \(g_i\) 的计算，朴素的做法是二维 DP，令 \(f_{i, j}\) 表示 DP 到 \(i\)，已经有了至多 \(j\) 对不同元素的方案数（发现这样才更好 DP）。发现没啥好的 \(O(n^2)\) 转移，只能 \(O(n^3)\)：
\[ f_{i,j}=\sum_{k<i}f_{k, j-1}\times \min\{A_{k+1\cdots i}\} \]
一个适用于容斥 DP 的 nb 优化：发现系数只取决于 \(j\) 维的奇偶性，发现转移也只关注奇偶性，故设 \(f_{i,0/1}\) 减少一维。
同时，很显然存在一个单调栈优化的结构，这样就可以在 \(O(n)\) 内完成 DP。
#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::vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
struct node { int mn; long long c0, c1; };
std::stack<node> st;
std::vector<std::array<long long, 2> > f(n + 1);
f[0][0] = 1ll, f[0][1] = 0ll;
auto s0 = 0x3f3f3f3fll, s1 = 0ll;
st.push({ 0x3f3f3f3f, 1ll, 0ll });
for (int i = 1; i <= n; ++i) {
auto p0 = 0ll, p1 = 0ll;
for (; !st.empty(); ) {
auto [mn, c0, c1] = st.top();
if (mn <= a[i])
break;
st.pop();
p0 += c0, p1 += c1;
(s0 += mod - c0 * (mn - a[i]) % mod) %= mod;
(s1 += mod - c1 * (mn - a[i]) % mod) %= mod;
}
st.push({ a[i], p0 % mod, p1 % mod });
f[i][0] = s1, f[i][1] = s0;
(s0 += f[i][0] * 0x3f3f3f3f % mod) %= mod;
(s1 += f[i][1] * 0x3f3f3f3f % mod) %= mod;
st.push({ 0x3f3f3f3f, f[i][0], f[i][1] });
}
std::cout << (f[n][n & 1] + mod - f[n][(n & 1) ^ 1]) % 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 - Unbranched
https://www.luogu.com.cn/problem/AT_abc180_f
注意到只会有环和链两种情况。发现消耗的点数和边数是不同的，再加上题目有边数限制，令 \(f_{i,j}\) 表示消耗了 \(i\) 个点 \(j\) 条边时的方案数。
转移是显然的：
对于环的情况，答案为圆排列去掉翻折，即 \(\dfrac {(k-1)!}2\)。特别地，二元环的圆排列不存在翻折，故答案为 \(1\)。
对于链的情况，去掉翻折即可，答案为 \(\dfrac {k!}2\)。
去重，参考典型的图计数问题，钦定没被选的点中，标号最小的必须被选，所以会有 \(C(n-(i-k)-1,k-1)\) 的系数。
显然对于最大值恰好为 \(L\) 的限制可以直接记一个
bool量在状态里；尊重一下容斥的标题，用 \(L\) 的答案减去 \(L-1\) 的答案亦可。
#include <bits/stdc++.h>
const int mod = 1e9 + 7;
const int inv2 = (mod + 1) >> 1;
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, L;
std::cin >> n >> m >> L;
using arr = std::vector<long long>;
using brr = std::vector<arr>;
using crr = std::vector<brr>;
arr fac(n + 1);
brr C(n + 1, arr(n + 1));
fac[0] = 1ll, C[0][0] = 1ll;
for (int i = 1; i <= n; ++i) {
C[i][0] = 1ll;
fac[i] = fac[i - 1] * i % mod;
for (int j = 1; j <= i; ++j)
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
}
crr f(n + 1, brr(m + 1, arr(2)));
f[0][0][0] = 1ll;
auto work = [&](int i, int j, int k, int p1, int p2) {
if (k == 1)
f[i][j][p2] += f[i - 1][j][p1];
else if (k == 2) {
if (j >= 2)
f[i][j][p2] += f[i - 2][j - 2][p1] * C[n - (i - k) - 1][k - 1] % mod;
if (j >= 1)
f[i][j][p2] += f[i - 2][j - 1][p1] * C[n - (i - k) - 1][k - 1] % mod;
}
else {
if (j >= k)
f[i][j][p2] += f[i - k][j - k][p1] * C[n - (i - k) - 1][k - 1] % mod * fac[k - 1] % mod * inv2 % mod;
if (j >= k - 1)
f[i][j][p2] += f[i - k][j - k + 1][p1] * C[n - (i - k) - 1][k - 1] % mod * fac[k] % mod * inv2 % mod;
}
return;
};
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= m; ++j) {
for (int k = 1; k <= i && k <= L; ++k)
if (k == L)
work(i, j, k, 0, 1), work(i, j, k, 1, 1);
else
work(i, j, k, 0, 0), work(i, j, k, 1, 1);
f[i][j][0] %= mod, f[i][j][1] %= mod;
}
std::cout << f[n][m][1] << '\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 - 局部极小值
https://www.luogu.com.cn/problem/P3160
重要性质：一个合法棋盘，
X的数量不会超过八个，故一个想法是只考虑X填的数，进而想到容斥钦定至少有某些位置是
X进行容斥，结合上面的性质发现空棋盘上的合法超集共 1000 多个，故可做，考虑单步钦定状态下的答案。令 \(f_{i,S}\) 表示填了 \(j\) 个数，目前
X集合已经填完了 \(S\) 内元素的方案数。
A - 数列
https://www.luogu.com.cn/problem/P7961
发现比较合理的 DP 方式是，令 \(f_{i,j,k,l}\) 表示当前正在 DP \(i\) 这个值，已经填了 \(j\) 个数，\(2^i\) 的个数，加上『进位』上来的，一共有 \(k\) 个，\(2^0\sim 2^i\) 总共有 \(l\) 个 1 的答案。那么有：
\[ f_{i+1,j+c,\left\lfloor\frac k2\right\rfloor+c,l+\left(\left\lfloor\frac k2\right\rfloor+c\right)\bmod 2}\gets f_{i,j,k,l}\times {v_{i + 1}}^c\times (c!)^{-1} \]
其中 \((c!)^{-1}\) 为多重集排列。最后乘上 \(n!\) 即可。
最后若 \(l+\text{ctz}\left(\left\lfloor\frac k2\right\rfloor\right)\le K\) 即可统计 \(f_{m,n,k,l}\) 的贡献。
注意到 \(k\) 维始终不超过 \(n\)，故复杂度 \(O(mn^3K)\)，非常可过。
#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, s;
std::cin >> n >> m >> s;
using arr = std::vector<long long>;
using brr = std::vector<arr>;
brr v(m + 1, arr(n + 1));
for (int i = 0; i <= m; ++i) {
v[i][0] = 1ll;
std::cin >> v[i][1];
for (int j = 2; j <= n; ++j)
v[i][j] = v[i][j - 1] * v[i][1] % mod;
}
arr inv(n + 1);
inv[0] = 1ll;
auto fac = 1ll;
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;
};
for (int i = 1; i <= n; ++i) {
(fac *= i) %= mod;
inv[i] = qkp(fac, mod - 2);
}
using crr = std::vector<brr>;
std::vector<crr> f(m + 1, crr(n + 1, brr(n + 1, arr(s + 1))));
for (int i = 0; i <= n; ++i)
f[0][i][i][i & 1] = v[0][i] * inv[i] % mod;
for (int i = 0; i < m; ++i)
for (int j = 0; j <= n; ++j)
for (int k = 0; k <= n; ++k)
for (int l = 0; l <= s; ++l) {
f[i][j][k][l] %= mod;
for (int c = 0; j + c <= n && k / 2 + c <= n && l + (k / 2 + c) % 2 <= s; ++c)
f[i + 1][j + c][k / 2 + c][l + (k / 2 + c) % 2] += f[i][j][k][l] * v[i + 1][c] % mod * inv[c] % mod;
}
auto res = 0ll;
for (int k = 0; k <= n; ++k)
for (int l = 0; l <= s; ++l)
if (l + __builtin_popcount(k / 2) <= s)
res += f[m][n][k][l] % mod;
std::cout << res % mod * fac % 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 - Vasya and Array
https://www.luogu.com.cn/problem/CF1093F
发现正着做避免不了记录相同段长度，所以考虑反过来容斥。
会发现这是一个类似于两双手的容斥结构。
两双手还在输出令 \(f_{i,j}\) 表示前 \(i\) 个均合法，且第 \(i\) 个元素为 \(j\) 的方案数，考虑什么时候会出现『前 \(i-1\) 个元素合法，到了第 \(i\) 个非法』的情况
发现即当前 \(i\) 前面有 \(len-1\) 个相同元素，且第 \(i\) 个成为第 \(len\) 个相同元素的情况。
显然有转移：
\[ f_{i,j}\gets \left(\sum_l f_{i-1,l}\right)-\left(\sum_{l\ne j} f_{i-len,l}\right)\times [a_{i-len+1\cdots i} = j\text{ is available}] \]
记录一下 \(s_i=\sum\limits_{j}f_{i,j}\) 的值即可做到 \(O(nk)\)。
#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, k, L;
std::cin >> n >> k >> L;
std::vector<int> a(n + 1);
std::vector<std::vector<int> > cnt(n + 1, std::vector<int> (k + 1));
for (int i = 1; i <= n; ++i) {
std::cin >> a[i];
for (int j = 1; j <= k; ++j)
cnt[i][j] = cnt[i - 1][j] + (a[i] == j);
cnt[i][0] = cnt[i - 1][0] + (a[i] == -1);
}
using arr = std::vector<long long>;
using brr = std::vector<arr>;
arr s(n + 1);
brr f(n + 1, arr(k + 1));
s[0] = 1ll;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= k; ++j)
if (a[i] == -1 || a[i] == j) {
f[i][j] = s[i - 1];
if (i >= L && (cnt[i][j] - cnt[i - L][j]) + (cnt[i][0] - cnt[i - L][0]) == L) {
f[i][j] += mod - (s[i - L] - f[i - L][j]);
if (s[i - L] < f[i - L][j])
f[i][j] -= mod;
if (f[i][j] >= mod)
f[i][j] -= mod;
}
s[i] += f[i][j];
if (s[i] >= mod)
s[i] -= mod;
}
std::cout << s[n] << '\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 - Road of the King
https://www.luogu.com.cn/problem/AT_codefestival_2016_final_f
发现最后的图是强连通的，当且仅当所有点都能走到 1。
最开始转化成『所有点都能通过操作序列走到 1』，错麻了 /qd
令 \(f_{i,j,k}\) 表示前 \(i\) 步，已经使得 \(j\) 个点能走到 1，当前已经访问过了 \(k\) 个不能走到 \(1\) 的点。
如果再次访问 \(j\) 个点中的其中一个，那么这 \(k\) 个点就能走到 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 n, m;
std::cin >> n >> m;
using arr = std::vector<long long>;
using brr = std::vector<arr>;
std::vector<brr> f(m + 1, brr(n + 1, arr(n + 1)));
f[0][1][0] = 1ll;
for (int i = 0; i < m; ++i)
for (int j = 1; j <= n; ++j) {
for (int k = 0; k + j <= n && k + j <= i + 1; ++k) {
f[i][j][k] %= mod;
f[i + 1][j][k] += f[i][j][k] * k % mod;
f[i + 1][j + k][0] += f[i][j][k] * j % mod;
if (j + k != n)
f[i + 1][j][k + 1] += f[i][j][k] * (n - j - k) % mod;
}
}
std::cout << f[m][n][0] % 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 - チーム分け
https://www.luogu.com.cn/problem/AT_mujin_pc_2018_f
很容易得到一个 \(O(n^3)\) 的做法：给 \(a\) 排序，从大到小选每个组的『限制者』。
\(f_{i,j}\) 表示选到 \(i\)，还剩 \(j\) 个 \(\ge a_i\) 的人没有分组，则：
\[ f_{i-1,j+1-k}\gets f_{i,j}\quad(1\le k\le a_i)\\ f_{i-1,j+1}\gets f_{i,j} \]
后面这个优化还是很难想的…… 主要是要注意到，可以不必在某个 \(a_i\) 处钦定其为『限制者』；而是在某个 \(i\) 处，给『未分组』的人分大小为 \(i\) 的组，而不关心具体谁是限制者，甚至不关心限制者的 \(a\) 值。
记 \(c_i\) 表示 \(i\) 处有几个 \(a\)，做多重集组合。仍然记录未分组人数 \(j\)，那么一个固定的 \(j\) 能贡献的大小为 \(i\) 的组满足调和级数，枚举组数 \(k\)，有：
\[ f_{i-1,j+c_i-k\cdot i}\gets f_{i+1,j}\times \binom{j+c_i}{i\cdot k}\times \frac{(i\cdot k)!}{(i!)^k\times k!}\quad\left(k\le \frac{j+c_i}i\right) \]
一定要注意分母里的 \(k!\) 的含义（消序）！组是无序的。
复杂度 \(O(n^2\log n)\)。
#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::vector<int> c(n + 1);
for (int i = 1, x; i <= n; ++i)
std::cin >> x, ++c[x];
using arr = std::vector<long long>;
using brr = std::vector<arr>;
brr C(n + 1, arr(n + 1));
C[0][0] = 1ll;
for (int i = 1; i <= n; ++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;
}
arr fac(n + 1);
fac[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;
};
brr pw(n + 1, arr(n + 1));
for (int i = 0; i <= n; ++i) {
pw[i][0] = 1ll, pw[i][1] = qkp(fac[i], mod - 2);
for (int j = 2; j <= n; ++j)
pw[i][j] = pw[i][j - 1] * pw[i][1] % mod;
}
brr f(n + 2, arr(n + 1));
f[n + 1][0] = 1ll;
for (int i = n; i; --i)
for (int j = 0; j + c[i] <= n; ++j)
for (int k = 0, l = (j + c[i]) / i; k <= l; ++k)
(f[i][j + c[i] - k * i] += f[i + 1][j] * C[j + c[i]][i * k] % mod * fac[i * k] % mod * pw[i][k] % mod * pw[k][1] % mod) %= mod;
std::cout << f[1][0] << '\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;
}E - Random Isolation
https://www.luogu.com.cn/problem/AT_arc165_e
发现期望可以拆贡献，每个局面下，每个大小 \(>K\) 的连通块恰好贡献 1 次操作次数。
这里提一下，一开始有这样的想法：每个存在 \(>K\) 连通块的局面都可以操作 1 次，所以一个局面有 1 的贡献；这是否和上面得到的结论矛盾？
答案是，统计局面的方案数权值和连通块的方案数权值是不一样的，但总和是一样的。且局面没什么好的统计方法，故统计连通块。
令 \(f_{x,i,j}\) 表示 \(x\) 为根，子树内选了大小为 \(i\) 的连通块，一共需要删除 \(j\) 个点。那么相当于要求这 \(j\) 个点的删除时间早于 \(i\) 内所有点。树上背包统计方案数，每个点处计算权值与贡献即可。
最后算权值的时候，把操作序列看成后几项无效的排列，那么要求这 \(j\) 个点的操作序列需要在所有 \(i\) 个点的前面
可以猜到一个答案：\(\dfrac {i!\times j!}{(i+j)!}\)。
但仔细想来并站不住脚：每个连通块的后几项在实际操作序列里是不存在的，整个操作序列的长短甚至都是未知的，好像没什么道理。
问了一圈没人说出来个靠谱的证明。算了。
#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, k;
std::cin >> n >> k;
std::vector<std::vector<int> > g(n + 1);
for (int i = 1, x, y; i < n; ++i) {
std::cin >> x >> y;
g[x].push_back(y), g[y].push_back(x);
}
using arr = std::vector<long long>;
using brr = std::vector<arr>;
brr C(n + 1, arr(n + 1));
for (int i = 0; i <= n; ++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 qkp = [&](long long x, int y) {
auto res = 1ll;
for (; y; (x *= x) %= mod, y >>= 1)
if (y & 1)
(res *= x) %= mod;
return res;
};
arr 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;
inv[i] = qkp(fac[i], mod - 2);
}
std::vector<int> siz(n + 1);
brr h(n + 1, arr(n + 1));
std::vector<brr> f(n + 1, brr(n + 1, arr(n + 1)));
auto res = 0ll;
std::function<void(int, int)> DFS = [&](int x, int fa) {
f[x][1][(int)g[x].size()] = 1ll;
siz[x] = 1;
for (auto i : g[x])
if (i != fa) {
DFS(i, x);
h = f[x];
for (int j = siz[x]; j; --j)
for (int a = 0; a < n; ++a)
if (f[x][j][a + 1])
for (int k = siz[i]; ~k; --k)
for (int b = 0; a + b < n; ++b)
f[x][j + k][a + b] += h[j][a + 1] * f[i][k][b + 1] % mod;
siz[x] += siz[i];
}
for (int i = 1; i <= siz[x]; ++i)
for (int j = 0; j <= n; ++j)
f[x][i][j] %= mod;
for (int i = k + 1; i <= siz[x]; ++i)
for (int j = 0; i + j <= n; ++j)
res += f[x][i][j] * fac[i] % mod * fac[j] % mod * inv[i + j] % mod;
res %= mod;
return;
};
DFS(1, -1);
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;
}A - 染色问题
https://www.luogu.com.cn/problem/P6076
题述转化成：恰好 \(n\) 行，恰好 \(m\) 列，恰好 \(c\) 种颜色即可容斥
将无色视为一个不参与容斥的颜色，容易写出答案式：
\[ \sum_{i=0}^{n}\sum_{j=0}^{m}\sum_{k=0}^{c} (-1)^{i+j+k}\times \binom ni\times \binom mj\times \binom ck\times (c-k+1)^{(n-i)(m-j)} \]
预处理幂次即可。复杂度 \(O(nmc)\)。
#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, m, c;
std::cin >> n >> m >> c;
std::vector<long long> 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 || m < 0)
return 0ll;
return fac[n] * inv[m] % mod * inv[n - m] % mod;
};
std::vector<std::vector<long long> > pw(c + 2, std::vector<long long> (n * m + 1));
for (int i = 1; i <= c + 1; ++i) {
pw[i][0] = 1ll;
for (int j = 1; j <= n * m; ++j)
pw[i][j] = pw[i][j - 1] * i % mod;
}
auto res = 0ll;
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= m; ++j)
for (int k = 0; k <= c; ++k) {
int op = ((i + j + k) & 1) ? mod - 1 : 1;
res += op * C(n, i) % mod * C(m, j) % mod * C(c, k) % mod * pw[c - k + 1][(n - i) * (m - j)] % 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 - Painting The Wall
https://www.luogu.com.cn/problem/CF398B
观察到初始被标记的行列之间等价，相似地，初始未被标记的行列之间等价。故可以粗暴地塞到状态里。
参照 Game with Probability Problem 中解决自转移的思路，考虑解方程。
设 \(f_{i,j}\) 表示剩余 \(i\) 行 \(j\) 列时的期望操作数，列出 DP 式：
\[ f_{i,j} \]
