COGS 2396. [HZOI 2015]有标号的强连通图计数 I

【题目描述】
求n个点的有向图中强连通图的个数，输出答案对10007取模后得结果(无重边，无自环)

定义强连通图为本身是一个强连通分量的图

【输入格式】
输入一个n表示节点个数

【输出格式】
输出题目要求的答案

【样例输入】

【样例输出】

【提示】
样例解释：

只有一个图，即有边<1,2>和边<2,1>

对于30%的数据，n<=7

对于100%的数据，n<=1000

---------------------------------

几个月之前想过强连通图的计数问题，发现根本不可做，暑假集训突然就变成作业了……
这道题的容斥姿势太高超了，功力不够学不来QWQ。
考虑模仿弱连通DAG计数，我们用总的减去不合法的。
考虑不合法的方案，在DAG计数中我们枚举的是出度为$0$的点。
我们类比一下，枚举出度为$0$的强连通分量。

额……看起来我们要计算$k$个点组成一些强连通分量(至多$k$个)的方案数了，但是如果类比DAG的容斥这是不够的，要计算出$k$个点组成$x$个强连通分量的方案数才能容斥。

不过先不着急，我们来理一下关系。

我们设$n$个点组成一个强连通分量的方案为$f(n)$。
定义$f(0)=0$。
设$n$个点有向图的个数为$h(n)$
$h(n)$是好计算的：$h(n)=2^{n(n-1)}$
在这里我们定义$h(0)=1$
那么模仿DAG，用合法减去不合法：

$f(n)=h(n)-$**没有组成强连通分量的方案**

现在就要考虑这个**没有组成强连通分量的方案**怎么算了。
仔细思考会发现我们根本不用得到$k$个点组成$x$个强连通分量的方案。模仿DAG计数，我们只需要强连通分量的块数是奇数有$+1$的贡献，块数是偶数有$-1$的贡献就行了，这里的块数就是DAG计数的点数！更通俗的说，这道题相当于我们从枚举点数的角度计算，但是同时也考虑到块数的容斥系数。而DAG的块数和点数就是一种东西，所以简单了很多。

那么设$g(n)$表示$n$个点组成奇数个联通块的种类数往上加，偶数个连通块的种类数往下减，最后得到的结果，定义$g(0)=0$。

同DAG计数：
$$f(n)=h(n)-\sum^n_{k=0} \binom n k 2^{k(n-k)}h(n-k)g(k)+f(n)$$

一定注意这个$+f(n)$!
考虑上式含义，枚举有$k$个点组成新的出度为$0$的强连通分量，另$n-k$个点可以任意连边也就是$h(n-k)$，这两部分可以任意连边$2^{k(n-k)}$，因为我们从枚举点数来考虑，所以把块数的容斥系数放在$g(k)$中。不过为什么要$+f(n)$呢？
因为我们容斥出的结果包含**只有一个连通块**的情况，也就是答案，但实际上这是合法的。
把两边的$f(n)$消掉，我们得到了关于$g(n)$和$h(n)$的式子：
$$\sum^{n}_{k=0} \binom n k 2^{k(n-k)}h(n-k)g(k)=h(n)$$
考虑把$g(n)$拿出来，发现$k=n$时$g(n)$的系数就是$1$
$$h(n)-\sum^{n-1}_{k=0} \binom n k 2^{k(n-k)}h(n-k)g(k)=g(n)$$
我们得到了$g(n)$的递推式。
通过考虑$f(n)$得到了$g(n)$的递推式，那么我们考虑$g(n)$会不会得到$f(n)$的递推式呢？
是的，考虑$f$,$g$的关系，我们枚举$1$号点所在的连通块大小：
$$g(n)=f(n)-\sum^{n}_{k=0}\binom {n-1} {k-1}f(k)g(n-k)$$
解释这个式子的含义:
因为$g(n)=$**1块方案**-**2块方案**+**3块方案**...
首先$f(n)$只有一个连通块，贡献就是$f(n)$。
后面因为在枚举过程中新加了$f(k)$这个连通块所以原来偶数的变成奇数，奇数变成偶数，所有的贡献都取了相反数，因此减去。
因为定义了$g(0)=0$，所以上式相当于
$$g(n)=f(n)-\sum^{n-1}_{k=0}\binom {n-1} {k-1}f(k)g(n-k)$$
得到$f(n)$递推式：
$$f(n)=g(n)+\sum^{n-1}_{k=0}\binom {n-1} {k-1}f(k)g(n-k)$$
这样我们就可以做了。

```
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
#define For(i, a, b) for(register int i = a; i <= b; ++i)
#define Down(i, a, b) for(register int i = a; i >= b; --i)
using namespace std;
const int maxn = 1e5 + 5;
const int mod = 10007;
int f[maxn], g[maxn], n, rw, ans[maxn];
int step[maxn], inv[maxn];
int fpow(int a, int b) {
    int ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod, b >>= 1;
    }
    return ans;
}
void pre(int n) {
    step[0] = inv[0] = 1;
    For(i, 1, n) step[i] = step[i - 1] * i % mod;
    inv[n] = fpow(step[n], mod - 2);
    Down(i, n - 1, 1) inv[i] = inv[i + 1] * (i + 1) % mod;
}
int C(int n, int m) {
    return 1ll * step[n] * inv[n - m] * inv[m] % mod;
}int pow2(int x) {
    return fpow(2, x);
}
int h(int n) {
    if(n == 0) return 1;
    return pow2((n - 1) * n % (mod - 1));
}
signed main() {
    //freopen("QAQ_strong_one.in", "r", stdin);
    //freopen("QAQ_strong_one.out", "w", stdout);
    f[1] = 1, g[1] = 1;
    f[0] = 0, g[0] = 0;
    scanf("%d", &n), pre(n);
    for(register int i = 2; i <= n; ++i) {
        g[i] = h(i);
        for(register int j = 1; j < i; ++j)
            g[i] -= ((pow2(j * (i - j) % (mod - 1)) * C(i, j) % mod)
            * h(i - j) % mod) * g[j] % mod;
        g[i] %= mod;
    }
    for(register int i = 2; i <= n; ++i) {
        f[i] = g[i];
        for(register int j = 1; j < i; ++j)
            f[i] += ((C(i - 1, j - 1) * f[j] % mod)) * g[i - j] % mod;
        f[i] %= mod;
    }
    printf("%d", (f[n] + mod) % mod);
    return 0;
}
```

Rockdu's Blog

导航

最近发表

大佬们的友链