623E

myee · 2021-09-22 22:03:50 · 题解

Update

dp 式没有使用函数形式，否则会与生成函数混淆，请注意。

前言

手推了好久柿子才推出来，结果最后一步不会，最后看了题解才知道是倍增。

所以，这算一个教训吧。

思路

以下默认 b_0=0。

首先 n>k 显然无解，原理是每次 n 加一必然多至少一位值为 1。

我们设 f_{n,k} 为恰好占用了 k 个二进制位时长度为 n 的序列的方案数。特别的，n>k 时 f_{n,k}=0。

由定义，我们有

ans=\sum_{i=0}^{k}\binom kif_{n,i}

我们发现一个 dp 式：

f_{n,k}=\sum_{i=0}^{k-1}\binom ki2^if_{n-1,i}

为啥我感觉这个很难想啊（~~因为我最开始没加这个二项式系数，推了 114514 秒后得到了一个假柿子~~），简要说说原理：

枚举 b_{n-1} 已经占有的位数 i（f_{n-1,i}），同时枚举是哪 i 位（\binom ki），那么这 i 位 a_n 既可占有亦可不占有（2^i）。
此外 k-i 位必须占有。

然后，设 \operatorname{EGF}：

\hat f_n(x)=\sum_{k=0}^{+\infty}f_{n,k}{x^k\over k!}

那么：

\hat f_n(x)=\sum_{k=0}^{+\infty}{x^k\over k!}\sum_{i=0}^{k-1}{k!\over i!\times(k-i)!}2^i[{x^i\over i!}]\hat f_{n-1}(x)

=\sum_{k=0}^{+\infty}x^k\sum_{i=0}^{k-1}{1\over (k-i)!}\times{2^i\over i!}[{x^i\over i!}]\hat f_{n-1}(x)

=\sum_{k=0}^{+\infty}x^k\sum_{i=0}^{k-1}{1\over (k-i)!}[x^i]\hat f_{n-1}(2x)

=\sum_{i=0}^{+\infty}x^i[x^i]\hat f_{n-1}(2x)\sum_{k=i+1}^{+\infty}x^{k-i}{1\over (k-i)!}

=\sum_{i=0}^{+\infty}x^i[x^i]\hat f_{n-1}(2x)\sum_{k=1}^{+\infty}{x^k\over k!}

=(e^x-1)\sum_{i=0}^{+\infty}x^i[x^i]\hat f_{n-1}(2x)

=(e^x-1)\hat f_{n-1}(2x)

即，\hat f_n(x)=(\exp x-1)\hat f_{n-1}(2x)。

边界 \hat f_0(x)=1。

展开来，我们有

\hat f_n(x)=\prod_{i=0}^{n-1}(e^{2^ix}-1)

而我们要求的，就是

ans=\sum_{i=0}^{k}\binom ki[{x^i\over i!}]\hat f_n(x)=k!\sum_{i=0}^{k}{[x^i]\hat f_n(x)\over(k-i)!}

因此只要能卷出 f_n(x) \bmod x^{k+1} 就可得答案。

由展开式，我们有：

\hat f_{2n}(x)=\hat f_n(x)\times\hat f_n(2^nx)

又有

\hat f_{2n+1}(x)=\hat f_{2n}(x)\times(e^{2^{2n}x}-1)

于是可以倍增或者递归卷出 \hat f_n(x)。我采用了后者。

时间复杂度：

T(n)=T(\frac n2)+O(n\log n)=O(n\log n)

Code

模数 1000000007 太吐了，要 MTT。

代码太长了，扔剪贴板里了。

链接。

核心代码的伪代码：

Integer n,k;
poly f(Integer n)
    if n == 1
        poly ans = "x"
        ans = exp(ans) - 1
        Make deg(ans) = k
        return ans
    poly ans, g
    g = f(n/2)
    ans = g
    Modint w, p
    w = pow(2, n/2)
    p = 1
    for Integer i from 0 to k
        g[i] = g[i] * p
        p = p * w
    ans = ans * g
    Make deg(ans) = k
    if n % 2 == 1
        g = pow(2, n/2) * "x"
        g = exp(g) - 1
        Make deg(g) = k
        ans = ans * g
        Make deg(ans) = k
    return ans
main()
    Input n, k
    if n > k
        Output 0
        return
    poly w = f(n)
    Modint ans
    ans = 0
    for Integer i from n to k
        ans = ans + Inv((k-i)!) * w[i]
    ans = ans * k!
    Output ans

总结

开头说了，我没有想到倍增。

这题说明了如何快速卷出出自倍增式的多项式组的指定项。

这确实算是一个教训吧。