ZOJ4069 Sub-cycle Graph

Feb 14, 2019 由 小羊

是时候回顾一波青岛站打铁时没想出来的题了QAQ。

题目传送门：ZOJ4069

求由 $n$ 个点组成 $k$ 条链，形成的所有图的方案数，对 1e9+7 取模。

首先，我们先考虑由 $m$ 个点形成 $1$ 条链的不同方案个数。显然对任意排列，去除倒过来的那个就行了。将方案数记为 $l_m$，则可以得到

$l_m = \begin{cases} 1, & m=1 \\ \frac{m!}{2}, & m>1 \end{cases}$

那么似乎接下来就是求它的生成函数了。在这里我们选择它的指数型生成函数。

$L(x) = \sum_{m=1}^\infty l_m \frac{x^m}{m!} = \frac{1}{2}\left(2x+x^2+x^3+\cdots\right) = x\left(1-\frac{x}{2}\right)\frac{1}{1-x}$

那么现在取 $k$ 条链，我们可以计算出

$A_k(x) = \sum_{n=1}^\infty a_{n,k} \frac{x^n}{n!} = \left[L(x)\right]^k = x^k \left(1-\frac{x}{2}\right)^k \left(\frac{1}{1-x}\right)^k$

由于这 $k$ 条链之间是不考虑先后关系的，所以

$b_{n,k} = \frac{a_{n,k}}{k!}$

就是最终的答案。

考虑一下题目是多测的，而且测试样例数高达 $T = 2 \times 10^4$，是不能进行FFT的。

我们可以发现

$\left(1-\frac{x}{2}\right)^k = \sum_{s=0}^k C_k^s \left(-\frac{1}{2}\right)^s x^s$

是可以用二项式定理做出来的。

然后考虑一下，后面的 $1/(1-x)^k$ 与前面这项进行卷积，其实就相当于对前面的数列进行了 $k$ 次前缀和。

emmmmm，看到网上有个dalao说

求k次前缀和的第m项，想必现在是个人都应该会了

突然自闭.jpg。然后推了推。假设这个数列原来是

$\lbrace x_0, x_1, x_2, \cdots \rbrace$

对它进行 $k+1$ 次前缀和，它会变成

$\lbrace C_k^k x_0, C_{k+1}^k x_0 + C_k^k x_1, C_{k+2}^k x_0 + C_{k+1}^k x_1 + C_k^k x_2, \cdots \rbrace$

即第 $n$ 项为

$\sum_{i=0}^n C_{k+i}^k x_{n-i}$

单次询问复杂度是 $O(m)$ 的，那么现在可以开始写代码啦！

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int MAXN = 1e5+5;
const int MOD = 1e9+7;
lld fac[MAXN], inv[MAXN], invs[MAXN];

inline void init()
{
    fac[0] = invs[0] = 1;
    fac[1] = inv[1] = invs[1] = 1;

    for (int i = 2; i < MAXN; i++)
    {
        fac[i] = i * fac[i-1] % MOD;
        inv[i] = (MOD-MOD/i) * inv[MOD%i] % MOD;
        invs[i] = inv[i] * invs[i-1] % MOD;
    }
}

inline lld C(int n, int k)
{
    if (n < k) return 0;
    return fac[n] * invs[k] % MOD * invs[n-k] % MOD;
}

void solve()
{
    int n, m, k;
    scanf("%d %d", &n, &m);

    if (m > n)
    {
        printf("0\n");
    }
    else if (m == n)
    {
        printf("%lld\n", fac[n-1]*inv[2]%MOD);
    }
    else
    {
        k = n - m;
        lld ans = 0, inv2s = 1;

        for (int i = m; i >= 0; i--)
        {
            ans += C(k-1+i,i) * C(k, m-i) % MOD * inv2s % MOD;
            inv2s = inv2s * (MOD-inv[2]) % MOD;
        }

        ans = (ans % MOD + MOD) % MOD;
        ans = ans * fac[n] % MOD * invs[k] % MOD;
        printf("%lld\n", ans);
    }
}

int main()
{
    init();
    int T; scanf("%d", &T);
    while (T--) solve();
    return 0;
}