Codeforces 997D Cycles in product
一道不难的 \(\texttt{DP}\) 题，但模拟赛时没做出来/kk ( 大概是一直在思考线性代数了 ) 。
首先可以将两棵树拆开来算贡献。设 \(A_i(k)\) 为树 \(T_i\) 上走出长度为 \(k\) 的环的方案数，\(A(k)\) 为树 \(T_1\times T_2\) 上走出长度为 \(k\) 的环的方案数，则 \(A(k)=\sum\limits_{i=0}^k\dbinom{k}{i}A_1(i)A_2(k-i)\)。考虑如何计算 \(A_i(k)\)。
一个很显然的想法是设 \(f_{u,k}\) 表示从 \(u\) 点开始走 \(k\) 步回到 \(u\) 点的方案数，且只在开头和结尾经过 \(u\) 点；\(F_{u,k}\) 表示从 \(u\) 点开始走 \(k\) 步回到 \(u\) 点的方案数，且中间可以经过 \(u\) 任意多次。那么 \(F_u\) 可以由 \(f_u\) 做完全背包得到。最后的 \(A_i(k)=\sum\limits_{j=1}^nF_{j,k}\)。考虑如何计算 \(f_{u}\)。
注意从 \(u\) 点开始是有可能向父结点走的，因此我们不能直接对 \(f\) 做子树 \(\text{DP}\)。我们可以将向父结点走的这种情况单独计算，即设 \(g'_{u,k}\) 表示从 \(u\) 开始第一步向其父结点走，经过 \(k\) 步之后回到 \(u\)，且只在开头和结尾经过 \(u\) 点；设 \(f'_{u,k}\) 表示从 \(u\) 开始第一步向其子结点走，……。那么就有 \(f_{u,k}=f'_{u,k}+g'_{u,k}\)。于是考虑如何计算 \(f'_{u,k},g'_{u,k}\)。
设 \(F'_{u}\) 是由 \(f'_u\) 做完全背包得到的。对 \(f'\) 做树形背包转移，有 \(f'_{u,k}\leftarrow f'_{u,i}+F'_{v,k-i}\)。于是 \(f'\) 就求完了。\(g'\) 也类似：设 \(G'_u\) 是由 \(g'_u\) 做完全背包得到的，则有 \(g'_{u,k}\leftarrow g'_{u,i}+F'_{v,k-i}\quad(v\in \operatorname{ch}_{\operatorname{fa}_u})\) 或 \(g'_{u,k}\leftarrow g'_{u,i}+G'_{\operatorname{fa}_u,k-i}\)。于是 \(g'\) 也求完了。
总时间复杂度为 \(\mathcal O(nk^2)\)。
参考代码
#include <bits/stdc++.h>
using namespace std;
static constexpr int mod = 998244353;
inline int add(int x, int y) { return x += y - mod, x + (x >> 31 & mod); }
inline int sub(int x, int y) { return x -= y, x + (x >> 31 & mod); }
inline int mul(int x, int y) { return (int64_t)x * y % mod; }
inline void add_eq(int &x, int y) { x += y - mod, x += (x >> 31 & mod); }
inline void sub_eq(int &x, int y) { x -= y, x += (x >> 31 & mod); }
inline void mul_eq(int &x, int y) { x = (int64_t)x * y % mod; }
static constexpr int Maxn = 4005, Maxk = 80, N = 4000, K = 75;
int binom[Maxk][Maxk];
namespace solver {
int n, K, en, head[Maxn];
struct Edge { int to, nxt; } e[Maxn * 2];
void add_edge(int u, int v) { e[++en] = (Edge){v, head[u]}, head[u] = en; }
int f[Maxn][Maxk], g[Maxn][Maxk], F[Maxn][Maxk], G[Maxn][Maxk], sF[Maxn][Maxk];
void dfs1(int u, int fa) {
f[u][0] = F[u][0] = 1;
for (int i = head[u], v; i; i = e[i].nxt)
if ((v = e[i].to) != fa) {
dfs1(v, u);
for (int j = 2; j <= K; ++j)
add_eq(f[u][j], F[v][j - 2]);
}
for (int j = 2; j <= K; j += 2)
for (int k = 2; k <= j; k += 2)
add_eq(F[u][j], mul(F[u][j - k], f[u][k]));
for (int i = head[u], v; i; i = e[i].nxt)
if ((v = e[i].to) != fa)
for (int j = 0; j <= K; j += 2)
add_eq(sF[u][j], F[v][j]);
} // dfs1
void dfs2(int u, int fa) {
for (int i = head[u], v; i; i = e[i].nxt)
if ((v = e[i].to) != fa) {
g[v][0] = G[v][0] = 1;
for (int j = 2; j <= K; j += 2)
g[v][j] = add(sub(sF[u][j - 2], F[v][j - 2]), G[u][j - 2]);
for (int j = 2; j <= K; j += 2)
for (int k = 2; k <= j; k += 2)
add_eq(G[v][j], mul(G[v][j - k], g[v][k]));
dfs2(v, u);
}
} // dfs2
void main(int _nn, int _kk, int *ans) {
n = _nn, K = _kk; en = 0, memset(head, 0, sizeof(head));
for (int i = 2, u, v; i <= n; ++i)
scanf("%d%d", &u, &v), add_edge(u, v), add_edge(v, u);
memset(f, 0, sizeof(f));
memset(F, 0, sizeof(F));
memset(sF, 0, sizeof(sF));
memset(g, 0, sizeof(g));
memset(G, 0, sizeof(G));
dfs1(1, 0);
dfs2(1, 0);
for (int i = 1; i <= n; ++i)
for (int j = 2; j <= K; j += 2)
add_eq(f[i][j], G[i][j - 2]);
memset(F, 0, sizeof(F));
for (int i = 1; i <= n; ++i) F[i][0] = 1;
for (int j = 2; j <= K; j += 2)
for (int k = 2; k <= j; k += 2)
for (int i = 1; i <= n; ++i)
add_eq(F[i][j], mul(F[i][j - k], f[i][k]));
fill(ans + 1, ans + K + 1, 0);
for (int j = 0; j <= K; j += 2)
for (int i = 1; i <= n; ++i)
add_eq(ans[j], F[i][j]);
} // solver::main
} // namespace solver
int main(void) {
for (int i = binom[0][0] = 1; i <= K; ++i)
for (int j = binom[i][0] = 1; j <= i; ++j)
binom[i][j] = add(binom[i - 1][j - 1], binom[i - 1][j]);
int n1, n2, m; scanf("%d%d%d", &n1, &n2, &m);
static int a1[Maxk], a2[Maxk], ans[Maxk];
solver::main(n1, m, a1);
solver::main(n2, m, a2);
for (int k = 2; k <= m; k += 2)
for (int i = 0; i <= k; ++i)
add_eq(ans[k], mul(binom[k][i], mul(a1[i], a2[k - i])));
printf("%d\n", ans[m]);
exit(EXIT_SUCCESS);
} // main