Edge Groups(ICPC)
2022/4/21 23:12:37
本文主要是介绍Edge Groups(ICPC),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
树上计数
考虑如果一个点的亲儿子是偶数个 两两亲儿子配对就好
如果一个点的亲儿子是奇数个 挑一个出来和连上父亲 其余偶数个两两配对
n个两两配对的方案数为 (C(n,2)×C(n-2,2)×...×C(2,2))/((n/2)!)
化简得 (n!)/(2的n/2次方)×((n/2)!)预处理阶乘就好
#include<bits/stdc++.h> using namespace std; #define lowbit(x) x&(-x) #define ll long long const int mod=998244353; const int maxn=1e5+5; int n; vector<int>Q[maxn]; ll ans=1; ll dp[maxn],jc[maxn],vis[maxn],cf[maxn]; ll fast_mi(ll aa, ll bb){ ll res=1; while(bb){ if(bb&1)res=res*aa%mod; bb>>=1; aa=aa*aa%mod; } return res; } void dfs(int u,int fa); ll calc(ll x){ return jc[x]*fast_mi(cf[x/2]*jc[x/2]%mod,mod-2)%mod; } int main(){ int n; jc[0]=1; cf[0]=1; cin>>n; for(int i=1;i<n;i++){ jc[i]=jc[i-1]*i%mod; cf[i]=cf[i-1]*2%mod; int a,b; cin>>a>>b; Q[a].push_back(b); Q[b].push_back(a); } jc[n]=jc[n-1]*n%mod; cf[n]=cf[n-1]*2%mod; dfs(1,1); for(int i=1;i<=n;i++) ans=ans*dp[i]%mod; cout<<ans<<endl; return 0; } void dfs(int u,int fa){ ll res=0; ll sz=Q[u].size()-1; for(int i=0;i<Q[u].size();i++){ int to=Q[u][i]; if(to==fa)continue; dfs(to,u); res+=vis[to]; } if(u==1)sz++; ll t=sz-res; if(t&1){ dp[u]=t*calc(t-1)%mod; vis[u]=1; }else dp[u]=calc(t); }
这篇关于Edge Groups(ICPC)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升
- 2024-05-08代码报错不用愁,CodeGeeX一键完成代码修复、错误解释的功能上线了!
- 2024-05-08今天开始程序员不用再发愁写commit message了,全部由CodeGeeX自动完成!