Consider an undirected, complete, simple graph G on n vertices. The vertices of G are labeled from 1 to n. Specifically, each pair of distinct vertices is connected by a single undirected edge, so there are precisely n*(n-1)/2 edges in this graph.
You are given a set E that contains some edges of the graph G. More precisely, you are given the vector s x and y. For each valid i, (x[i], y[i]) is one of the edges in E.
A spanning tree of G is a subset of exactly n-1 edges of G such that the edges connect all n vertices. You may note that the edges of a spanning tree do indeed form a tree that is a subgraph of G and spans all its vertices.
We are interested in spanning trees that contain all of the edges in the provided set E. Compute and return the number of such spanning trees modulo 987,654,323. Two spanning trees are different if there is an edge of G that is in one of them but not in the other.
Definition
Class:
BuildingSpanningTreesDiv1
Method:
getNumberOfSpanningTrees
Parameters:
int, vector , vector
Returns:
int
Method signature:
int getNumberOfSpanningTrees(int n, vector x, vector y)
(be sure your method is public)
Limits
Time limit (s):
2.000
Memory limit (MB):
256
Notes
987,654,323 is a prime number.
Constraints
n will be between 1 and 1,000, inclusive.
x will contain between 1 and 1,000 elements, inclusive.
y will contain between 1 and 1,000 elements, inclusive.
x and y will contain the same number of elements.
Each element of x will be between 1 and n-1, inclusive.
Each element of y will be between 2 and n, inclusive.
For each valid i, x[i] will be less than y[i].
All edges in E will be distinct.
Examples
0)
3
{1,2}
{2,3}
Returns: 1
The edges in the provided set E alredy form a spanning tree, so there is exactly one spanning tree that contains them.
1)
5
{1,3,4}
{2,4,5}
Returns: 6
There are six ways to add the one missing edge: one endpoint of the new edge must lie in the set {1,2} and the other in the set {3,4,5}.
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stdint.h>
#include <string>
#include <utility>
#include <vector>
using namespace std;
int const MAX_N = 1003;
int const MOD = 987654323;
int p [MAX_N];
int s [MAX_N];
int root (int v)
{
if (p[v] != v)
{
p[v] = root (p[v]);
}
return p[v];
}
bool unite (int u, int v)
{
u = root (u);
v = root (v);
if (u == v)
{
return false;
}
p[v] = u;
s[u] += s[v];
return true;
}
int powmod (int a, int b)
{
int res = 1;
for ( ; b > 0; b >>= 1)
{
if (b & 1)
{
res = (res * 1LL * a) % MOD;
}
a = (a * 1LL * a) % MOD;
}
return res;
}
int a [MAX_N] [MAX_N];
int n;
int det (void)
{
int res = 1;
for (int i = 1; i < n; i++)
{
int j;
for (j = i; j < n; j++)
{
if (a[j][i])
{
break;
}
}
if (j == n)
{
return 0;
}
if (j != i)
{
for (int k = i; k < n; k++)
{
swap (a[i][k], a[j][k]);
}
}
res = (res * 1LL * a[i][i]) % MOD;
int inv = powmod (a[i][i], MOD - 2);
for (int j = i + 1; j < n; j++)
{
int mult = (a[j][i] * 1LL * inv) % MOD;
for (int k = i; k < n; k++)
{
a[j][k] = (a[j][k] -
a[i][k] * 1LL * mult) % MOD;
}
}
}
return (res + MOD) % MOD;
}
class BuildingSpanningTreesDiv1
{
public:
int getNumberOfSpanningTrees (int n, vector <int> x, vector <int> y)
{
for (int i = 0; i < n; i++)
{
p[i] = i;
s[i] = 1;
}
int k = (int) (x.size ());
for (int w = 0; w < k; w++)
{
int u = x[w] - 1;
int v = y[w] - 1;
if (!unite (u, v))
{
return 0;
}
a[u][v] += 1;
a[v][u] += 1;
a[u][u] -= 1;
a[v][v] -= 1;
}
int t = 0;
for (int i = 0; i < n; i++)
{
if (p[i] == i)
{
s[t] = s[i];
t += 1;
}
}
n -= k;
::n = n;
memset (a, 0, sizeof (a));
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
int e = s[i] * s[j];
a[i][j] -= e;
a[j][i] -= e;
a[i][i] = (a[i][i] + e) % MOD;
a[j][j] = (a[j][j] + e) % MOD;
}
}
int res = det ();
return res;
}
};
const int mod = 1000000009;
long long quickpow(long long a, long long b) {
if (b < 0) return 0;
long long ret = 1;
a %= mod;
while(b) {
if (b & 1) ret = (ret * a) % mod;
b >>= 1;
a = (a * a) % mod;
}
return ret;
}
long long inv(long long a) {
return quickpow(a, mod - 2);
}
(2)扩展欧几里得算法求逆元
可扩展欧几里得求逆元ax≡1(mod n)其中a，n互质；
复杂度：O(logn)；
1234567891011121314151617
ll extend_gcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
else {
ll r = extend_gcd(b, a % b, y, x);
y -= x * (a / b);
return r;
}
}
ll inv(ll a, ll n) {
ll x, y;
extend_gcd(a, n, x, y);
x = (x % n + n) % n;
return x;
}
(3) 逆元线性筛 ( P为质数 )
求1,2,…,N关于P的逆元（P为质数）
复杂度：O(N)
代码：
123456
const int mod = 1000000009;
const int maxn = 10005;
int inv[maxn];
inv[1] = 1;
for(int i = 2; i < 10000; i++)
inv[i] = inv[mod % i] * (mod - mod / i) % mod;
