BZOJ 2467 生成树(组合数学)-白红宇

BZOJ 2467 生成树(组合数学)

阅读量：4963 次

发布时间：2019-06-12

本文共 1137 字，大约阅读时间需要 3 分钟。

题意：求n-五边形的生成树个数。

结论题，答案为4*n*5^(n-1).

首先中心的n边形一定需要切掉一个边，C(1,n).

然后每个五边形都切一个边，C(1,4)*5^(n-1).

于是答案就是4*n*5^(n-1).

# include 
      
       # include 
       
        # include 
        
         # include 
         
          # include 
          
           # include 
           
            # include 
            
             # include 
             # include 
              
               # include 
               
                # include 
                
                 # include 
                 
                  using namespace std;# define lowbit(x) ((x)&(-x))# define pi acos(-1.0)# define eps 1e-8# define MOD 2007# define INF 1000000000# define mem(a,b) memset(a,b,sizeof(a))# define FOR(i,a,n) for(int i=a; i<=n; ++i)# define FO(i,a,n) for(int i=a; i
                  
                    PII;typedef vector
                   
                     VI;# pragma comment(linker, "/STACK:1024000000,1024000000")typedef long long LL;int Scan() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}const int N=105;//Code begin...int mod[N];int main (){ int T, n; scanf("%d",&T); mod[0]=1; FOR(i,1,100) mod[i]=mod[i-1]*5%MOD; while (T--) { scanf("%d",&n); printf("%d\n",4*n*mod[n-1]%MOD); } return 0;}