🌑

小羊儿的心情天空

ZOJ4069 Sub-cycle Graph

Feb 14, 2019 由 小羊

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

题目传送门:ZOJ4069

求由 nn 个点组成 kk 条链,形成的所有图的方案数,对 1e9+7 取模。

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

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

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

L(x)=m=1lmxmm!=12(2x+x2+x3+)=x(1x2)11xL(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}

那么现在取 kk 条链,我们可以计算出

Ak(x)=n=1an,kxnn!=[L(x)]k=xk(1x2)k(11x)kA_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

由于这 kk 条链之间是不考虑先后关系的,所以

bn,k=an,kk!b_{n,k} = \frac{a_{n,k}}{k!}

就是最终的答案。

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

我们可以发现

(1x2)k=s=0kCks(12)sxs\left(1-\frac{x}{2}\right)^k = \sum_{s=0}^k C_k^s \left(-\frac{1}{2}\right)^s x^s

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

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

emmmmm,看到网上有个dalao说

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

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

{x0,x1,x2,}\lbrace x_0, x_1, x_2, \cdots \rbrace

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

{Ckkx0,Ck+1kx0+Ckkx1,Ck+2kx0+Ck+1kx1+Ckkx2,}\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

即第 nn 项为

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

单次询问复杂度是 O(m)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;
}