首页 > 代码库 > 2016弱校联盟十一专场10.2——Around the World
2016弱校联盟十一专场10.2——Around the World
题目链接：Around the World
题意：
给你n个点，有n-1条边，现在这n-1条边又多增加了ci*2-1条边，问你有多少条欧拉回路
题解：
套用best定理
Best Theorem：有向图中以 i 为起点的欧拉回路个数为以 i 为根的树形图个数 ×(( 每个点 度数 −1)!)。
Matrix Tree Theorem：以 i 为根的树形图个数 = 基尔霍夫矩阵去掉第 i 行第 i 列的行列 式。
从某个点 i 出发并回到 i 的欧拉回路个数 = 以 i 为起点的欧拉回路个数 ×i 的度数。
1 #include<cstdio> 2 #include<cstring> 3 #define F(i,a,b) for(int i=a;i<=b;i++) 4 typedef long long ll; 5 6 const int N=1e5+7,P=1e9+7,M=2e6; 7 long long fact[M+1]; 8 int deg[N],n; 9 10 ll qpow(ll a,ll n){11 ll ans=1;12 while(n){13 if(n&1) ans=ans*a%P;14 a=a*a%P,n>>=1;15 }16 return ans;17 }18 ll C(int n,int m){return (fact[n]*qpow(fact[m],P-2)%P)*qpow(fact[n-m],P-2)%P;}19 20 int main(){21 fact[0]=1;22 F(i,1,2000000)fact[i]=fact[i-1]*i%P;23 scanf("%d",&n);24 ll ans=1;25 memset(deg,0,sizeof(deg));26 F(i,1,n-1){27 int a,b,c;28 scanf("%d%d%d",&a,&b,&c);29 deg[a]+=c,deg[b]+=c,ans=(ans*C(2*c,c)%P)*c%P;30 }31 F(i,1,n)ans=ans*fact[deg[i]-1]%P;32 printf("%lld\n",ans*deg[1]%P);33 return 0;34 }
2016弱校联盟十一专场10.2——Around the World
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。