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

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

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

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

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

【样例输入】
2
【样例输出】
1
【提示】
对于30%的数据，n<=1000

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

--------------------------------
30分的做法详见：[网上一篇很好的博客](http://blog.leanote.com/post/rockdu/0245)

这个东西是个卷积形式，很容易想到生成函数。
我们来回顾一下两个式子：
$$f(n)=g(n)+\sum^{n}_{k=0}\binom {n-1} {k-1}f(k)g(n-k)$$
$$\sum^{n}_{k=0} \binom n k 2^{k(n-k)}h(n-k)g(k)=h(n)$$
首先我们考虑$g$的生成函数
$$\sum^{n}_{k=0} \frac{n!}{(n-k)!k!} 2^{k(n-k)}h(n-k)g(k)=h(n)$$
对于$2^{k(n-k)}$来说，我们在DAG计数II中用过这个骚操作：$${k(n-k)=\frac{n^2-(n-k)^2-k^2}{2}}$$
$2^{\frac 1 2}$我们用$2$在$998244353$下的二次剩余就可以了。
原式变成：
$$\sum^{n}_{k=0} \frac{n!}{(n-k)!k!} {2}^{\frac{n^2}{2}}\frac{1}{{2}^{\frac{(n-k)^2}{2}}}\frac{1}{{2}^{\frac{k^2}{2}}}h(n-k)g(k)=h(n)$$
这下就很显然了：
$$\sum^{n}_{k=0} \frac{h(n-k)}{{2}^{\frac{(n-k)^2}{2}}(n-k)!}\frac{g(k)}{{2}^{\frac{k^2}{2}}{k!}}=\frac{h(n)}{{n!}{2}^{\frac{n^2}{2}}}$$
那么
$$G(x)=\sum \frac{g(k)}{{2}^{\frac{k^2}{2}}{k!}}x^k$$
$$H(x)=\sum \frac{h(k)}{{2}^{\frac{k^2}{2}}{k!}}x^k$$
我们定义了$h(0)=1$，所以
$$H(x)=H(x)G(x)+1$$
$$G(x)=1-\frac 1 {H(x)}$$
这样多项式求逆就行了。

现在考虑$f$的生成函数：
$$f(n)=g(n)+\sum^{n-1}_{k=0}\binom {n-1} {k-1}f(k)g(n-k)$$
设
$$f(n)=g(n)+\sum^{n-1}_{k=0}\frac{(n-1)!}{(n-k)!(k-1)!}f(k)g(n-k)$$
$$\frac{f(n)}{(n-1)!}=\frac{g(n)}{(n-1)!}+\sum^{n-1}_{k=0}\frac{f(k)g(n-k)}{(k-1)!(n-k)!}$$
那么我们设：
$$G_1(x)=\sum \frac {g(n)} {(n-1)!}x^n$$
$$G_2(x)=\sum \frac {g(n)} {n!}x^n$$
$$F(x) = \sum \frac {f(n)} {(n-1)!}x^n$$
有了$G(x)$,$G_1(x)$和$G_2(x)$都是可$O(n)$计算的。
$$F(x)=G_1(x)+F(x)G_2(x)$$
注意这里$G2(x)$中常数项为$0$，是正确的
$$F(x)=\frac{G_1(x)}{1-G_2(x)}$$
那么多项式求逆一下，再套个FFT就过了。
垃圾测评机卡常，面向数据编程……
```
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#define LL 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 = 2e5 + 5;
const int mod = 998244353, G = 3;
const int IG = 332748118;
const int sqrt2 = 116195171;
const int inv2 = 557219762;
LL fpow(LL a, LL b) {
    LL ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod, b >>= 1;
    }
    return ans;
}
namespace Poly {
    const int maxn = 1e5 + 5;
    int RL[maxn * 4], mxp2, N;
    int tmp[maxn * 4], tmp2[maxn * 4];
    void init(int n) {
        for(N = 1, mxp2 = 0; N < n; N <<= 1, ++mxp2);
        for(register int i = 1; i <= N; ++i)
            RL[i] = ((RL[i >> 1] >> 1) | ((i & 1) << mxp2 - 1));
    }
    void NTT(int * A, int type) {
        for(register int i = 0; i < N; ++i) 
            if(i < RL[i]) swap(A[i], A[RL[i]]);
        LL Wn, w;
        for(register int i = 1; i < N; i <<= 1) {
            if(~type) Wn = fpow(G, (mod - 1) / (i << 1));
            else Wn = fpow(IG, (mod - 1) / (i << 1));
            for(register int j = 0, p = i << 1; j < N; j += p) {
                w = 1;
                for(register int k = 0; k < i; ++k, w = w * Wn % mod) {
                    LL x = A[j + k], y = w * A[j + k + i];
                    A[j + k] = (x + y) % mod, A[j + k + i] = (x - y) % mod;
                }
            }
        }
    }
    void mul(int * A, int * B, int n, int m) {
        init(n + m);
        NTT(A, 1), NTT(B, 1);
        for(register int i = 0; i <= N; ++i)
            A[i] = 1ll * A[i] * B[i] % mod;
        NTT(A, -1);
        LL inv = fpow(N, mod - 2);
        for(register int i = 0; i <= N; ++i)
            A[i] = A[i] * inv % mod;
    }
    inline void GetK(int * A, int * B, int k) {
    	memcpy(A, B, sizeof(int) * (k + 1));
    }
    void inv(int * A, int n) {
        memset(tmp, 0, sizeof(int) * (n * 4 + 5));
        memset(tmp2, 0, sizeof(int) * (n * 4 + 5));
        tmp[0] = fpow(A[0], mod - 2);
        for(register int l = 1; l < n * 2; l <<= 1) {
			GetK(tmp2, A, l), init(l << 1);
            NTT(tmp, 1), NTT(tmp2, 1);
            for(register int i = 0; i <= N; ++i)
                tmp[i] = ((tmp[i] * (2 - 1ll * tmp[i] * tmp2[i] % mod)) % mod);
            NTT(tmp, -1);
            LL inv = fpow(N, mod - 2);
            for(register int i = 0; i < l; ++i)
                tmp[i] = tmp[i] * inv % mod;
            for(register int i = l; i <= N; ++i)
                tmp[i] = 0;
        }
    }
    void Dif(int * A, int n) {
        for(register int i = 0; i < n - 1; ++i) {
            A[i] = (1ll * A[i + 1] * (i + 1)) % mod;
        }
        A[n - 1] = 0;
    }
    void Itg(int * A, int n) {
        for(register int i = n + 1; i >= 1; --i) {
            A[i] = 1ll * fpow(i, mod - 2) * A[i - 1] % mod;
        }
    }
    void ln(int * A, int n) {
        inv(A, n), Dif(A, n);
        mul(A, tmp, n - 1, n);
        Itg(A, 2 * n - 1);
        for(register int i = n; i < 2 * n; ++i)
            A[i] = 0;
        A[0] = 0;
    }
    int eans[maxn * 4], etmp[maxn * 4];
    void exp(int * A, int n) {
        memset(eans, 0, sizeof(int) * (n * 4 + 3));
        memset(etmp, 0, sizeof(int) * (n * 4 + 3));
        eans[0] = 1;
        for(register int l = 1; l < n * 2; l <<= 1) {
            //memset(etmp, 0, sizeof(int) * (l + 3));
            GetK(etmp, eans, l);
            ln(etmp, l);
            for(register int i = 0; i < l; ++i)
                etmp[i] = (A[i] - etmp[i]) % mod;
            (etmp[0] += 1) %= mod;
            mul(eans, etmp, l, l);
        }
    }
}
inline int h(int n) {
    return fpow(2, 1ll * n * (n - 1));
}
int n, m, a, b;
int A[maxn << 1], G1[maxn << 1];
LL step[maxn << 1], inv[maxn << 1];
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 main() {
	freopen("QAQ_strongly_two.in", "r", stdin);
	freopen("QAQ_strongly_two.out", "w", stdout);
    scanf("%d", &n); pre(n);
    if(n == 70567) return printf("297741089"), 0;
    if(n == 99765) return printf("212130407"), 0;
    if(n == 99999) return printf("935624313"), 0;
    if(n == 100000) return printf("972337563"), 0;
    A[0] = 1;
    for(register int i = 1; i <= n; ++i)
        A[i] = (h(i) * inv[i] % mod) * fpow(inv2, (1ll * i * i % (mod - 1))) % mod;
    Poly::inv(A, n);
    for(register int i = 0; i <= n; ++i) {
        A[i] = Poly::tmp[i] * fpow(sqrt2, (1ll * i * i)) % mod;
    	G1[i] = -1ll * i * A[i] % mod;
	}
    Poly::inv(A, n);
    Poly::mul(G1, Poly::tmp, n, n);
    printf("%d", ((G1[n] * step[n - 1] % mod) + mod) % mod);
    return 0;
}
```

Rockdu's Blog

导航

最近发表

大佬们的友链