首页 > 代码库 > BZOJ2467 [中山市选2010]生成树
BZOJ2467 [中山市选2010]生成树
本文版权归ljh2000和博客园共有,欢迎转载,但须保留此声明,并给出原文链接,谢谢合作。
本文作者:ljh2000
作者博客:http://www.cnblogs.com/ljh2000-jump/
转载请注明出处,侵权必究,保留最终解释权!
题目链接:BZOJ2467
正解:矩阵树定理 or 组合数学
解题报告:
这道题有两种做法…
一种是建图,然后用$Matrix-Tree$定理强上,建出基尔霍夫矩阵,高斯消元,但是建图的话有点麻烦。
还有一种就是纯粹从组合数学的角度了:
考虑如果$n$个五边形每个断掉一条边就会得到一个基环外向树,此时还需要断掉一条边,这意味着$n$个五边形中就有一个五边形要断掉两条边,并且容易想到有一条必然是在中心的那个$n$边形上,那么就可以用组合数学来表示了。
从$n$个五边形中选取一个是选两条边的,这个五边形在中央$n$边形上那条边必选,那么只需在剩下$4$条边再断一条即可,而剩下的$n-1$个五边形都是随便断一条即可,
总方案数就是$4*n*5^{n-1}$。
//It is made by ljh2000 //有志者,事竟成,破釜沉舟,百二秦关终属楚;苦心人,天不负,卧薪尝胆,三千越甲可吞吴。 #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> #include <ctime> #include <vector> #include <queue> #include <map> #include <set> #include <string> #include <complex> #include <bitset> using namespace std; typedef long long LL; typedef long double LB; typedef complex<double> C; const double pi = acos(-1); const int mod = 2007; int n,ans; inline int getint(){ int w=0,q=0; char c=getchar(); while((c<‘0‘||c>‘9‘) && c!=‘-‘) c=getchar(); if(c==‘-‘) q=1,c=getchar(); while (c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar(); return q?-w:w; } inline int fast_pow(int x,int y){ int r=1; while(y>0) { if(y&1) r*=x,r%=mod; x*=x; x%=mod; y>>=1; } return r; } inline void work(){ int T=getint(); while(T--) { n=getint(); ans=4*n; ans*=fast_pow(5,n-1); ans%=mod; cout<<ans<<endl; } } int main() { work(); return 0; } //有志者,事竟成,破釜沉舟,百二秦关终属楚;苦心人,天不负,卧薪尝胆,三千越甲可吞吴。
BZOJ2467 [中山市选2010]生成树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。