4 个人，三种不同的公式

BEST 定理是什么？

# $\operatorname{ec}(G) = t _ w(G) \prod _ {v\in V} \bigl(\deg(v)-1\bigr)!$

#include <bits/stdc++.h>

#define NS (105)
#define MOD (1000003)
#define pls(a, b) ((a) + (b) < MOD ? (a) + (b) : (a) + (b) - MOD)
#define mns(a, b) ((a) - (b) < 0 ? (a) - (b) + MOD : (a) - (b))
#define mul(a, b) (1ll * (a) * (b) % MOD)

using namespace std;

template<typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

int n, D[NS][NS], deg[NS], ideg[NS], fac[200005];

int det()
{
int res = 1;
for (int i = 1; i < n; i += 1)
{
for (int j = i + 1; j < n; j += 1)
while (D[j][i])
{
int tmp = D[i][i] / D[j][i];
for (int k = i; k < n; k += 1)
D[i][k] = mns(D[i][k], mul(tmp, D[j][k]));
swap(D[i], D[j]), res = mns(0, res);
}
res = mul(res, D[i][i]);
}
return res;
}

int main(int argc, char const* argv[])
{
fac[0] = 1;
for (int i = 1; i <= 200000; i += 1) fac[i] = mul(fac[i - 1], i);
while(IN(n), n)
{
memset(D, 0, sizeof(D)), memset(ideg, 0, sizeof(ideg));
for (int i = 1; i <= n; i += 1)
{
IN(deg[i]);
for (int j = 1, k; j <= deg[i]; j += 1)
{
IN(k), ideg[k]++;
D[i][k] = mns(D[i][k], 1), D[k][k] = pls(D[k][k], 1);
}
}
if (n == 1) {printf("%d\n", fac[deg[1]]); continue;}
for (int i = 1; i <= n; i += 1)
if (deg[i] != ideg[i]) {puts("0"); continue;}
for (int i = 1; i < n; i += 1)
{
swap(D[i], D[i + 1]);
for (int j = 1; j <= n; j += 1) D[i][j] = D[i][j + 1];
}
int t = mul(det(), deg[1]);
for (int i = 1; i <= n; i += 1) t = mul(t, fac[deg[i] - 1]);
printf("%d\n", t);
}
return 0;
}


#### Remmina

No puzzle that couldn't be solved.

### 3 条评论

#### Remmina · 2021年3月29日 2:48 下午

看着自己以前写的感觉自己好幼稚啊 23333

#### ShuYuMo · 2021年3月29日 2:50 下午

幼稚归幼稚 但是比其他的博客确实会好一些 /CY 其他的没有讲清楚等价类的划分规则是什么 就很迷惑…