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定理做的话就很裸了，直接套板子就可以了
/**************************************************************
Problem: 2467
User: ictsing
Language: C++
Result: Accepted
Time:3324 ms
Memory:13128 kb
****************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int read()
{
int 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;
}
const int mt = 1000+5;
const int mod= 2007;
//const int P=mod;
int D[mt][mt],A[mt][mt],C[mt][mt];
int matrixtree(int n)
{
for(int i=1;i<n;i++)
for(int j=1;j<n;j++)
C[i][j]=(C[i][j]+mod)%mod;/**/
int ans=1;
for(int i=1;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
int a=C[i][i],b=C[j][i];
while(b)
{
int tmp=a/b;a%=b;//因为，而变量重名QAQ
for(int k=i;k<n;k++) C[i][k]=(C[i][k]-tmp*C[j][k])%mod;
for(int k=i;k<n;k++) swap(C[i][k],C[j][k]);
swap(a,b),ans=-ans;
}
}
if(!C[i][i]) return 0;
ans=ans*C[i][i]%mod;
}
return (ans+mod)%mod;
}
int main()
{
int t=read(),n,top;
while(t--)
{
memset(D,0,sizeof(D)),memset(A,0,sizeof(A));
n=read(),top=n;
for(int i=1;i<=n;i++)
{
int u=i,v=i+1>n?1:i+1;A[u][v]++,A[v][u]++,D[u][u]++,D[v][v]++;
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;
}
for(int i=1;i<=top;i++)
for(int j=1;j<=top;j++)
C[i][j]=D[i][j]-A[i][j];
printf("%d\n",matrixtree(top)%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
using namespace std;
int A[MAXN][MAXN],D[MAXN][MAXN],C[MAXN][MAXN];
int n,top;
int T;
int calc(int size)
{
for (int i=1;i<size;i++)
for (int j=1;j<size;j++)
C[i][j]=(C[i][j]+P)%P;
int ret=1;
for (int i=1;i<size;i++)
{
for (int j=i+1;j<size;j++)
{
int a=C[i][i],b=C[j][i];
while (b)
{
int temp=a/b;a%=b;swap(a,b);
for (int k=i;k<size;k++) C[i][k]=(C[i][k]-temp*C[j][k])%P;
for (int k=i;k<size;k++) swap(C[i][k],C[j][k]);
ret=-ret;
}
}
if (!C[i][i]) return 0;
ret=ret*C[i][i]%P;
}
return (ret+P)%P;
}
int main()
{
scanf("%d",&T);
while (T--)
{
memset(A,0,sizeof(A));memset(D,0,sizeof(D));
scanf("%d",&n);
top=n;
for (int i=1;i<=n;i++)
{
int u=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 (int i=1;i<=top;i++)
for (int j=1;j<=top;j++)
C[i][j]=D[i][j]-A[i][j];
cout<<calc(top)<<endl;
}
}
评论