BZOJ2467[中山市选2010]生成树

Description

有一种图形叫做五角形圈。一个五角形圈的中心有1个由n个顶点和n条边组成的圈。在中心的这个n边圈的每一条边同时也是某一个五角形的一条边,一共有n个不同的五角形。这些五角形只在五角形圈的中心的圈上有公共的顶点。如图0所示是一个4-五角形圈。

现在给定一个n五角形圈,你的任务就是求出n五角形圈的不同生成树的数目。还记得什么是图的生成树吗?一个图的生成树是保留原图的所有顶点以及顶点的数目减去一这么多条边,从而生成的一棵树。

注意:在给定的n五角形圈中所有顶点均视为不同的顶点。

 

Input

输入包含多组测试数据。第一行包含一个正整数T,表示测试数据数目。每组测试数据包含一个整数n( 2<=N<=100),代表你需要求解的五角形圈中心的边数。

 

 

Output

对每一组测试数据,输出一行包含一个整数x,表示n五角形圈的生成树数目模2007之后的结果。

Sample Input

1
2

Sample Output

40

HINT 

 

Source

 

Solution

组合数的方法是看Po姐的blog的,无限orz。。。。

拆掉两条边的五边形有n个可以选 第一条边拆掉中心多边形上的 第二条边有4条可以选
其余的五边形每个可以拆掉一条边 方案数5^(n-1)
故最终方案数为4n*5^(n-1)

matrix-tree定理做的话就很裸了,直接套板子就可以了


#include<iostream>
#include<cstdio>
using namespace std;
const int mod= 2007;
typedef long long ll;
ll readll()
{
ll num=0,flag=1;
char ch;
do{
  ch=getchar();
  if(ch=='-') flag=-1;
 }while(ch<'0'||ch>'9');
do{
     num=num*10+ch-'0';
  ch=getchar();
 }while(ch>='0'&&ch<='9');
return num*flag;
}
ll quickpow(ll a,ll b)
{
ll ans=1;
while(b)
 {
  if(b&1) ans=ans*a%mod;
  a=a*a%mod,b>>=1;
 }
return ans%mod;
}
int main()
{
ll t=readll();
while(t--)
 {
ll n=readll();
printf("%lld\n",4*n%mod*quickpow(5,n-1)%mod);
    }
return 0;
}


/**************************************************************

    Problem: 2467

    User: ictsing

    Language: C++

    Result: Accepted

    Time:3340 ms

    Memory:13244 kb

****************************************************************/

 

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#define MAXN 1010

#define P 2007

usingnamespacestd;

intA[MAXN][MAXN],D[MAXN][MAXN],C[MAXN][MAXN];

intn,top;

intT;

intcalc(intsize)

{

    for(inti=1;i<size;i++)

        for(intj=1;j<size;j++)

            C[i][j]=(C[i][j]+P)%P;

    intret=1;

    for(inti=1;i<size;i++)

    {

        for(intj=i+1;j<size;j++)

        {

            inta=C[i][i],b=C[j][i];

            while(b)

            {

                inttemp=a/b;a%=b;swap(a,b);

                for(intk=i;k<size;k++)    C[i][k]=(C[i][k]-temp*C[j][k])%P;

                for(intk=i;k<size;k++)    swap(C[i][k],C[j][k]);

                ret=-ret;

            }

        }

        if(!C[i][i])   return0;

        ret=ret*C[i][i]%P;

    }

    return(ret+P)%P;

}

intmain()

{

    scanf("%d",&T);

    while(T--)

    {

        memset(A,0,sizeof(A));memset(D,0,sizeof(D));

        scanf("%d",&n);

        top=n;

        for(inti=1;i<=n;i++)

        {

            intu=i,v=i+1>n?1:i+1;

            A[u][top+1]++;A[top+1][u]++;D[u][u]++;D[top+1][top+1]++;

            A[top+1][top+2]++;A[top+2][top+1]++;D[top+1][top+1]++;D[top+2][top+2]++;

            A[top+2][top+3]++;A[top+3][top+2]++;D[top+2][top+2]++;D[top+3][top+3]++;

            A[top+3][v]++;A[v][top+3]++;D[top+3][top+3]++;D[v][v]++;

            top+=3;

            A[u][v]++;A[v][u]++;D[u][u]++;D[v][v]++;

        }

        for(inti=1;i<=top;i++)

            for(intj=1;j<=top;j++)

                C[i][j]=D[i][j]-A[i][j];

        cout<<calc(top)<<endl;

    }

}

评论

热度(1)