首页 > 代码库 > BZOJ 2467 中山市选2010 生成树 组合数学
BZOJ 2467 中山市选2010 生成树 组合数学
题目大意:给定一个图,图的中心是一个n个点的多边形,每条边都外接一个五边形,求生成树个数
Matrix Tree定理?不会!
观察这个图
5n条边 4n个点
每个五边形都是一个环 必须拆掉一条边
拆掉之后发现4n个点 4n条边 是一个基环树
基环树的环上的边由中心多边形被拆掉的边所在的五边形的剩余边与中心多边形未被拆掉的边构成
容易发现这个环上任意拆掉一条边都会导致某个五边形被拆掉两条边 且一条边在中心多边形上
于是可知 这个图成为一棵树当且仅当一个五边形被拆掉两条边 剩余五边形被拆掉一条边 且被拆掉两条边的五边形拆掉的其中一条边在中心多边形上
拆掉两条边的五边形有n个可以选 第一条边拆掉中心多边形上的 第二条边有4条可以选
其余的五边形每个可以拆掉一条边 方案数5^(n-1)
故最终方案数为4n*5^(n-1)
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define MOD 2007 using namespace std; int Quick_Power(int x,int y) { int re=1; while(y) { if(y&1)re*=x,re%=MOD; x*=x,x%=MOD; y>>=1; } return re; } int main() { int n,T; for(cin>>T;T;T--) { scanf("%d",&n); printf("%d\n", 4*n%MOD*Quick_Power(5,n-1)%MOD ); } }
BZOJ 2467 中山市选2010 生成树 组合数学
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。