题意:
给定平面上N个点。如果两点距离小于等于R,且两点间线段上没有其他点的时候,两点可以建立一条边。得到这个图后,求此图的生成树个数 mod 10007,如果图不连通则输出-1.
先构图,再根据Matrix tree定理,求出Kirchhoff矩阵,然后用高斯消元求行列式的值(注意提取系数求逆元和交换两行要取反).
#include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> using namespace std; #define N 310 #define mod 10007 __int64 G[N][N]; bool v[N][N]; int n,r; int x[N],y[N]; int dis(int a,int b){ return (x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]); } __int64 gcd(__int64 a,__int64 b){ if(b==0) return a; return gcd(b,a%b); } __int64 Pow(__int64 a,int k){ __int64 c=1; a%=mod; while(k) { if(k&1) c=c*a%mod; k>>=1; a=a*a%mod; } return c; } __int64 lcm(__int64 a,__int64 b){ return a/gcd(a,b)*b; } __int64 Inv(__int64 v){ return Pow(v,mod-2); } __int64 det() { int i, j, k; __int64 ans=1; __int64 t; for(i = 1; i < n; i++) { int tmp; __int64 num = 0; for(j = i; j < n; j++) { if(abs(G[j][i]) > num) { num = abs(G[j][i]); tmp = j; } } if(num==0) return 0; ans = num*ans%mod; if(tmp != i) { for(k = i; k < n; k++) swap(G[i][k],G[tmp][k]); ans=(-ans%mod+mod)%mod; } for (j= i + 1; j < n; j++) { if (G[j][i] != 0) { __int64 LCM = lcm(abs(G[j][i]), abs(G[i][i])); __int64 ta = LCM / abs(G[j][i]), tb = LCM / abs(G[i][i]); ans=ans*Inv(ta)%mod; if (G[j][i] * G[i][i] < 0) tb=-tb; for (k= i; k<n; k++) { G[j][k]= (G[j][k] * ta - G[i][k]* tb)%mod; if(G[j][k]<0) G[j][k]+=mod; } } } } return ans%mod; } bool vis[N]; void dfs(int u){ vis[u]=1; for(int i=1;i<=n;i++) if(v[u][i]&&!vis[i]) dfs(i); } int main(){ int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&r); for(int i=1;i<=n;i++) { scanf("%d%d",x+i,y+i); } memset(G,0,sizeof(G)); memset(v,0,sizeof(v)); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) { if(dis(i,j)>r*r) continue ; int k; for( k=1;k<=n;k++) { if(k==i||k==j||x[k]<min(x[i],y[i])||x[k]>max(x[i],x[j])||y[k]<min(y[i],y[j])||y[k]>max(y[i],y[j])) continue; if((x[i]-x[k])*(y[j]-y[k])-(x[j]-x[k])*(y[i]-y[k])==0) break; } if(k>n) v[i][j]=v[j][i]=1; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { G[i][i]+=v[i][j]; if(i!=j) G[i][j]-=v[i][j]; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) G[i][j]=(G[i][j]+mod)%mod; memset(vis,0,sizeof(vis)); dfs(1); int i; for(i=1;i<=n;i++) if(!vis[i]) break; if(i<=n) puts("-1"); else { __int64 ans=det(); printf("%I64d\n",ans); } } }