Codeforces Round #564 (Div. 2) D(组合数学/树上DP)
2022/4/16 6:22:53
本文主要是介绍Codeforces Round #564 (Div. 2) D(组合数学/树上DP),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
D. Nauuo and Circle
题意:
给定一棵\(n\)个节点的树,从\(1\)到\(n\)编号,现在你需要玩弄这棵树。问按照顺时针遍历能获得多少种不同的序列。最后的答案对\(\%998244353\)
思路:
定义\(son[u]\)表示\(u\)的子节点的个数。先固定\(1\)是这个序列中的第一个,因为这是一个环所以最后的答案要乘上\(n\)。定义\(dp[u]\)表示的是以\(u\)为节点的方案数。
对于节点\(1\),我们可以就是对\(son[u]\)进行全排列,并将排列方式放在\(1\)的后面,将\(son[u]\)全排列一共有\(A_{son[u]} ^ {son[u]}\)种方案,也就是\(son[u]!\)种方案,而它的每一个儿子\(v\)同样也有它们的子节点,所以就得到了式子$$dp[u] = son[u]! * \prod_{v\in G[u]}{dp[v]}$$
而对于非\(1\)节点,它们自身也可以进行全排列所以对于非\(1\)的节点,它们的方案数的表达式是\(dp[u] = (son[u] + 1)! * \prod_{v\in G[u]}{dp[v]}\)
所以最后我们将两种情况合并就是$$dp[u] = du[u]! \prod_{v\in G[u]}{dp[v]}$$其中\(du[u]\)表示的是\(du[u]\)的度
void solve() { int n; std::cin >> n; fac[0] = 1; rep(i,1,N) fac[i] = fac[i - 1] * i; std::vector<int> G[n + 1], du(n + 1); rep(i,0,n - 1) { int u, v; std::cin >> u >> v; G[u].push_back(v), G[v].push_back(u); du[v] ++, du[u] ++; } std::vector<Z> dp(n + 1); std::function<void(int, int)> dfs = [&] (int u, int fa) -> void { Z res = 1; for (auto v : G[u]) { if (v == fa) continue; dfs(v, u); res = res * dp[v]; } dp[u] = fac[du[u]] * res; }; dfs(1, 0); Z ans = dp[1] * n; std::cout << ans.val() << "\n"; }
这篇关于Codeforces Round #564 (Div. 2) D(组合数学/树上DP)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享
- 2024-06-06基于 casdoor 的 ELK 开源登录认证解决方案: elk-auth-casdoor-icode9专业技术文章分享
- 2024-05-29Elasticsearch慢查询日志配置
- 2024-05-29揭秘华为如此多成功项目的产品关键——Charter模板
- 2024-05-29海外IDC业务拓展的7大挑战
- 2024-05-29InLine Chat功能优化对标Github Copilot,CodeGeeX带来更高效、更直观的编程体验!
- 2024-05-29CodeGeeX 智能编程助手 6 项功能升级,在Visual Studio插件市场霸榜2周!
- 2024-05-29AutoMQ 生态集成 Apache Doris
- 2024-05-292024年IDC行业的深度挖掘:机遇、挑战与未来展望
- 2024-05-29五款扩展组件齐发 —— Volcano、Keda、Crane-scheduler 等,邀你体验