P9669 [ICPC2022 Jinan R] DFS Order 2 题解
简要题意
给定一棵 \(n\) 个节点的树，根节点是 \(1\) 。
从根节点开始深度优先搜索这一棵树，dfs序是在搜索过程中访问节点的顺序。
对于每一个节点 \(v\) ，你要给出有多少种不同的dfs序，使得 \(v\) 出现在第 \(j\) 个位置。
答案对 \(998244353\) 取模。
解法说明
首先我们考虑一下总共有多少种dfs序。
记 \(h[x]\) 为只考虑 \(x\) 的子树内的节点所形成的dfs序的方案数。
假设 \(x\) 有 \(m\) 个儿子，那么他选第一个儿子的时候有 \(m\) 种选法，第二个儿子有 \(m - 1\) 种选法，同理第 \(i\) 个儿子有 \(m - i + 1\) 种选法，那么他儿子的选法总共有 \(m!\) 种。
然后再乘上他每个儿子的只考虑子树内节点形成dfs序的方案数。
我们可以得到 \(h[x] = jc[m]\times\prod\limits_{v \in e[x].v} h[v]\)。
其中 \(jc[i]\) 表示 \(i\) 的阶乘，\(e[x].v\) 表示 \(x\) 的儿子节点。
设 \(f[j][k]\) 表示在 \(x\) 的儿子中选了 \(j\) 个儿子， \(s\) 和为 \(k\) 的方案数。
其中 \(s[x]\) 表示 \(x\) 的子树中的总节点数。
\(f[j][k]\) 可以通过背包的方式来求出。
每一个 $j \in [1,m],k \in [s[v],n] $ 由 \(f[j - 1][k - s[v]],v \in e[x].v\) 转移而来。
因为我们把表示 \(x\) 的那一维滚掉了，所以我们需要逆序来算上面的 \(f[j][k]\)。
然后我们假设我们现在已经处理到 \(x\) 的儿子 \(v\) 这个节点。
设 \(g[k]\) 表示当前儿子节点 \(v\) 排在 \(x\) 后面 \(k\) 个位置的方案数, \(hx\) 为该节点除去儿子 \(v\) 的方案以及去掉选 \(m\) 个儿子的排列的方案。
我们知道 \(f[j][k]\) 是 \(x\) 的儿子中的总方案数，为了求出 \(v\) 节点排在父亲后的方案,我们需要求出除去 \(v\) 的方案数。
可以通过回退背包的做法，把 \(v\) 的贡献减掉。
对于每个状态 \(f[j][k]\) 我们把 \(f[j - 1][k - s[v]]\) 的贡献给减掉，上面加入贡献我们是逆序做的，这里需要正序来减。
总的方案每一次计算新的 \(v\) 都要使用，所以在这次的关于 \(v\) 的计算完成后，要把这里减掉的贡献重新加回去。
对于选择的节点数量 \(k \in [1,s[x]]\) 可以由不同的儿子节点的选择方式组成，那么 \(g[x]\) 可以从 \(f[j][k]\) 转移过来。
对于已选的 \(j\) 个儿子，有 \(j!\) 种选择，剩下的 \(m - j - 1\) 个儿子，有 \((m - j - 1)!\) 种选择。
然后再乘上 \(hx\) 就可以得到 \(g[x]\)。
这里的 \(hx = h[x] / h[v] / m!\) 是去除 \(v\) 的子树中，\(x\) 的子树中，其他节点的方案数。
现在我们求出了儿子节点排在父亲节点后 \(k\) 个位置的方案数了，那么我们便可以推出他在整棵树中dfs序的情况了。
设 \(dp[x][k]\) 表示 \(x\) 在总的dfs序中排在位置 \(k\) 的方案数（不计 \(x\) 子树内部节点方案数）。
每个儿子节点的位置都可以从他父亲的位置往后推出来，即 \(dp[v][j + k] = \sum\limits_{j\in[1,n],k\in[1,s[x]]} dp[x][j] * g[k]\)
然后 \(dp[i][j] * h[i]\) 即为题目要求的最终的方案数。
我们对于每一个节点 \(x\) 都要求一个 \(f[j][k]\)，每个 \(f[j][k]\) 都需要遍历 \(x\) 的儿子数以及所有的叶子节点数，这里的复杂度是 \(O(n^3)\) 的。
同理其他几个状态的转移复杂度和这个也是同级的，所以总复杂度为 \(O(n^3)\)。
原本对于每个 \(x\) 的每个 \(v\) 单独求解除去 \(v\) 的方案应该是 \(O(n^4)\) 的复杂度，这里使用了回滚背包，优化成了 \(O(n^3)\) 。
具体实现
#include<bits/stdc++.h>
#define int long long
using namespace std;
int read()
{
int s = 0,f = 1; char x = getchar();
while(x < '0' || '9' < x) f = (x == '-') ? -1 : 1 , x = getchar();
while('0' <= x && x <= '9') s = s * 10 + x - '0' , x = getchar();
return s * f;
}
const int N = 510;
const int mo = 998244353;
int n;
int s[N],ft[N];
int h[N],son[N];
int f[N][N];
int ans[N][N],dp[N][N];
int iv[N],fc[N];
vector <int> e[N];
int fpow(int x,int nn)
{
int res = 1;
while(nn)
{
if (nn & 1) res = (res * x) % mo;
x = (x * x) % mo;
nn >>= 1;
}
return res;
}
int inv(int x)//求逆元
{
if (x <= n) return (iv[x] * fc[x - 1]) % mo;
return fpow(x,mo - 2);
}
void dfs(int x,int fa)
{
ft[x] = fa;
s[x] = 1;
h[x] = 1;
for (int i = 0,v;i < e[x].size();i ++)
{
v = e[x][i];
if (v == fa) continue;
son[x] ++;
dfs(v,x);
h[x] = (h[x] * h[v]) % mo;//在x的子树内的方案数
s[x] += s[v];
}
h[x] = (h[x] * fc[son[x]]) % mo;
return;
}
void dfs1(int x)
{
int m = son[x];
vector<vector<int> > f(m + 1,vector<int>(s[x] + 1,0));
f[0][0] = 1;//不选儿子一种方案
for (int i = 0,v;i < e[x].size();i ++)
{
v = e[x][i];
if (v == ft[x]) continue;
for (int j = m;j >= 1;j --)
{
for (int k = s[x];k >= s[v];k --)
{
f[j][k] = (f[j][k] + f[j - 1][k - s[v]]) % mo;//选v这个儿子
}
}
}
for (int i = 0,v;i < e[x].size();i ++)
{
v = e[x][i];
if (v == ft[x]) continue;
int hx = (h[x] * inv(h[v]) % mo * iv[m]) % mo;//去掉儿子中v的方案数以及去掉 选m个儿子的排列的方案
for (int j = 1;j <= m;j ++)
for (int k = s[v];k <= s[x];k ++)
f[j][k] = ((f[j][k] - f[j - 1][k - s[v]]) % mo + mo) % mo;//去掉儿子v的方案数
vector <int> g(n + 1,0);//g[k]表示在x后k个位置的方案数
for (int j = 0;j < m;j ++)
for (int k = 0;k < s[x];k ++)
g[k + 1] = (g[k + 1] + f[j][k] * hx % mo * fc[j] % mo * fc[m - j - 1]) % mo;
for (int j = 1;j <= n;j ++)
for (int k = 1;k <= s[x];k ++)
dp[v][j + k] = (dp[v][j + k] + dp[x][j] * g[k]) % mo;
for (int j = m;j >= 1;j --)
for (int k = s[x];k >= s[v];k --)
f[j][k] = (f[j][k] + f[j - 1][k - s[v]]) % mo;
dfs1(v);
}
return;
}
signed main()
{
n = read();
fc[0] = 1;
for (int i = 1;i <= n + 1;i ++) fc[i] = (fc[i - 1] * i) % mo;
iv[n + 1] = fpow(fc[n + 1],mo - 2);
for (int i = n;i >= 0;i --) iv[i] = (iv[i + 1] * (i + 1)) % mo;//求阶乘逆元
for (int i = 1,u,v;i < n;i ++)
{
u = read() , v = read();
e[u].push_back(v) , e[v].push_back(u);
}
dfs(1,0);
dp[1][1] = 1;
dfs1(1);
for (int i = 1;i <= n;i ++)
{
for (int j = 1;j <= n;j ++)
{
ans[i][j] = (dp[i][j] * h[i]) % mo;
cout << ans[i][j] << ' ';
}
puts("");
}
return 0;
}
/*
5
1 2
1 3
3 4
3 5
*/
后话
这篇题解主要是参考了 2022 International Collegiate Programming Contest, Jinan Site C. DFS Order 2(树形dp+回滚背包) 和 2022 ICPC 济南站 C (回退背包) 还有 P9669 [ICPC2022 Jinan R] DFS Order 2 三位大佬的题解。
标签：ICPC2022,方案,int,题解,mo,Jinan,dfs,儿子,节点 From： https://www.cnblogs.com/9981day/p/17787907.html