KIDx的解题报告
?
题意:给出n个点,给出R,两点距离不大于R而且两点之间没其他点阻碍,就可以建一条边,问可以形成多少棵生成树,如果没有,输出-1,否则,输出(生成树个数 mod 10007)
?
典型的生成树计数:
①求出邻接矩阵G
②求出度数矩阵D
③D-G得出Kirchhoff矩阵
④求Kirchhoff矩阵任意n-1阶子矩阵的行列式
一些概念不懂的话还是要看看周冬的《生成树的计数及其应用》http://wenku.baidu.com/view/782ab9eb19e8b8f67c1cb9a9.html
?
当然取余方面要用到逆元的知识:
乘法逆元:
x*y ≡ 1mod (mod),则称 x 是 y 对于mod的乘法逆元
分数取模就要用到了,如求(a/b) % mod = ?
那就要先解决b^-1 % mod = ?
就等价于b的逆元x%mod了,求出x即可变为求a*x % mod = ?
令y = b,x*y ≡ 1mod (mod) → x*y + k*mod == 1
用扩展欧几里德即可算出y的逆元x
?
?#include <iostream>
using namespace std;
#define M 305
struct point{
int x, y;
}p[M];
int C[M][M], G[M][M];
int mod = 10007;
int dis (point a, point b)
{
return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
}
void Egcd (int a, int b, int &x, int &y)
{
if (b == 0)
{
x = 1, y = 0;
return ;
}
Egcd (b, a%b, x, y);
int tp = x;
x = y;
y = tp - a/b*y;
}
int det (int n) //计算n阶行列式
{
int i, j, k, ans = 1, x, y, flg = 1;
for (i = 0; i < n; i++)
{
if (C[i][i] == 0)
{
for (j = i+1; j < n; j++)
if (C[j][i])
break;
if (j == n) return -1;
flg = !flg;
for (k = i; k < n; k++)
swap (C[i][k], C[j][k]);
}
ans = ans * C[i][i] % mod;
Egcd (C[i][i], mod, x, y);
x = (x%mod + mod) % mod; //注意保证取余结果为最小非负数
for (k = i+1; k < n; k++)
C[i][k] = C[i][k] * x % mod;
for (j = i+1; j < n; j++)
if (C[j][i] != 0) for (k = i+1; k < n; k++)
C[j][k] = ((C[j][k] - C[i][k]*C[j][i])%mod + mod) % mod;
//注意保证取余结果为最小非负数
}
if (flg) return ans;
return mod-ans;
}
int main ()
{
int i, j, k, t, n, r;
scanf ("%d", &t);
while (t--)
{
scanf ("%d%d", &n, &r);
for (i = 0; i < n; i++)
scanf ("%d%d", &p[i].x, &p[i].y);
memset (G, 0, sizeof(G));
for (i = 0; i < n; i++) //建图
{
for (j = i + 1; j < n; j++)
{
int tp = dis (p[i], p[j]);
if (tp > r*r) continue;
for (k = 0; k < n; k++)
{
if (k == i || k == j) continue;
if ((p[i].x-p[k].x)*(p[j].y-p[k].y) ==
(p[j].x-p[k].x)*(p[i].y-p[k].y) &&
dis (p[i], p[k]) < tp && dis (p[j], p[k]) < tp)
break;
}
if (k == n) G[i][j] = G[j][i] = 1;
}
}
memset (C, 0, sizeof(C));
for (i = 0; i < n; i++)
for (j = i + 1; j < n; j++)
if (G[i][j])
++C[i][i], ++C[j][j];
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
{
C[i][j] -= G[i][j];
C[i][j] = (C[i][j]%mod + mod) % mod;
//注意保证取余结果为最小非负数
}
printf ("%d\n", det(n-1));
}
return 0;
}