HDU 4305 Lightning(生成ツリーのカウント+マトリクスツリー定理+逆元)

タイトルアドレス:http://acm.hdu.edu.cn/showproblem.php?pid=4305
标题:n個の点をあげて、もし2個の点の距離がr以下であれば、1本の辺をつなぎ、木の個数を求めさせます.
問題:
無方向図Gの場合、そのKirchhoff行列Cは、その度数行列Dからその隣接行列Aを減算するように定義される.明らかに、このような定義はさっき説明した性質を満たしている.
Kirchhoff行列というツールがあれば,Matrix‐Tree定理を導入できる.
行列のルールは次のとおりです.
1、主対角線上の要素このノードの度数
2、他の位置の要素Matrix(i,j)について { i != j },
   (1) ノードiとノードjとが連通場合、Matrix(i,j)の値は-kであり、kの値はノードiからノードjまでの平行辺の数である.この図が単純な図である、任意の2点間に平行辺が存在しない場合、この値は-1である.
   (2) しかし、ノードiとノードjがまったく連通していない場合、Matrix(i,j)の値は0となる.
求法:無方向図Gに対して、その生成木個数は、そのKirchhoff行列のいずれかのn-1次主子式の行列式の絶対値に等しい.n-1次主子式とは、いずれかのrに対して、Cのr行目とr列目を同時に削除した新しい行列をCrで表す.複雑度はO(n^3)である
ACコード:

#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iterator>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;


typedef long long LL;
const int N=302;
const LL mod=10007;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-7;
using namespace std;

int a[N][N],mp[N][N];
int n;
double r;

struct node
{
    double x,y;
    node(){};
    node(double a,double b):x(a),y(b){}
    void input()
    {
        scanf("%lf%lf",&x,&y);
    }
    friend node operator -(const node &a,const node &b)
    {
        return node(a.x-b.x,a.y-b.y);
    }
}p[N];

double dis(node a,node b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}

bool love(int i,int k,int j)
{
    double t=(p[i].x-p[k].x)*(p[j].y-p[k].y)-(p[i].y-p[k].y)*(p[j].x-p[k].x);
    if(fabs(t-0)>1e-6)
        return false;//       
    t=(p[i].x-p[k].x)*(p[j].x-p[k].x)+(p[i].y-p[k].y)*(p[j].y-p[k].y);
    if(t>=0)
        return false;//  ij  
    return true;
}

int ext_gcd(int a,int b,int &x,int &y)
{
    int t,ret;
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    ret=ext_gcd(b,a%b,x,y);
    t=x,x=y,y=t-a/b*y;
    return ret;
}

int gauss(int r,int c)
{
    int i=1,k,j,cnt=1;
    for(j=1;j<=c;j++)
    {
        int id=i;
        for(k=i;k<=r;k++)
            if(a[k][j]>0)
            {
                id=k;break;
            }
        if(a[id][j])
        {
            if(id!=i)
            {
                for(k=j;k<=c;k++)
                    swap(a[i][k],a[id][k]);
            }
            for(k=i+1;k<=r;k++)
            {
                if(!a[k][j])    continue;
                cnt=(cnt*a[i][j])%mod;
                for(int l=c;l>=j;l--)
                {
                    a[k][l]=(a[k][l]*a[i][j]-a[i][l]*a[k][j])%mod;
                    a[k][l]=(a[k][l]+mod)%mod;
                }
            }
            i++;
        }
    }
    int x,y;
    ext_gcd(cnt,mod,x,y);
    x=(x%mod+mod)%mod;//x cnt mod   
    for(i=1;i<=r;i++)
        x=(x*a[i][i])%mod;
    return (x+mod)%mod;
}

int main()
{
    int t,i,j,k,cas;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%lf",&n,&r);
        for(i=1;i<=n;i++)
            p[i].input();
        memset(a,0,sizeof(a));
        memset(mp,0,sizeof(mp));
        double rr=r*r;
        for(i=1;i<=n;i++)
            for(j=i+1;j<=n;j++)
            {
                if(dis(p[i],p[j])>rr)   continue;
                int flag=1;
                for(k=1;k<=n;k++)
                {
                    if(i==k||j==k)  continue;
                    //              ，     ，       A 
                    if(love(i,k,j))//k ij     
                    {
                        flag=0;
                        break;
                    }
                }
                if(flag)
                {
                    mp[i][j]=mp[j][i]=1;
                    a[i][j]--;  a[j][i]--;
                    a[i][i]++;  a[j][j]++;
                }
            }
        /*cout<<endl;
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
                printf("%d ",mp[i][j]);
            cout<<endl;
        }
        cout<<endl;
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
                printf("%d ",a[i][j]);
            cout<<endl;
        }*/
        int xh=gauss(n-1,n-1);
        if(xh==0)
            puts("-1");
        else
            printf("%d
",xh);
    }
    return 0;
}
/*
3
3 2
-1 0
0 1
1 0

3 2
-1 0
0 0
1 0

3 1
-1 0
0 1
1 0
*/