同见于我的洛谷博客

Update

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

前言

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

所以，这算一个教训吧。

思路

以下默认 $b_0=0b\_0=0$b0​=0。

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

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

由定义，我们有

$ans={\sum }_{i=0}^k\left(\frac{k}{i}\right)f_{n,i}ans=\backslash sum\_\{i=0\}^\{k\}\backslash binom\; kif\_\{n,i\}$ans=∑i=0k​(ik​)fn,i​

我们发现一个 dp 式：

$f_{n,k}={\sum }_{i=0}^{k-1}\left(\frac{k}{i}\right)2^i{f}_{n-1,i}f\_\{n,k\}=\backslash sum\_\{i=0\}^\{k-1\}\backslash binom\; ki2^if\_\{n-1,i\}$fn,k​=∑i=0k−1​(ik​)2ifn−1,i​

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

• 枚举 $b_{n-1}b\_\{n-1\}$bn−1​ 已经占有的位数 $ii$i（$f_{n-1,i}f\_\{n-1,i\}$fn−1,i​），同时枚举是哪 $ii$i 位（$\left(\frac{k}{i}\right)\backslash binom\; ki$(ik​)），那么这 $ii$i 位 $a_{n}a\_n$an​ 既可占有亦可不占有（$2^{i}2^i$2i）。
• 此外 $k-ik-i$k−i 位必须占有。

然后，设 $\mathrm{EGF}\backslash operatorname\{EGF\}$EGF：

${\widehat{f}}_n\left(x\right)={\sum }_{k=0}^{+\infty }{f}_{n,k}\frac{x^k}{k!}\backslash hat\; f\_n(x)=\backslash sum\_\{k=0\}^\{+\backslash infty\}f\_\{n,k\}\{x^k\backslash over\; k!\}$f^​n​(x)=∑k=0+∞​fn,k​k!xk​

那么：

${\widehat{f}}_n\left(x\right)={\sum }_{k=0}^{+\infty }\frac{x^k}{k!}{\sum }_{i=0}^{k-1}\frac{k!}{i!\times (k-i)!}{2}^i\left[\frac{x^i}{i!}\right]{\widehat{f}}_{n-1}\left(x\right)\backslash hat\; f\_n(x)=\backslash sum\_\{k=0\}^\{+\backslash infty\}\{x^k\backslash over\; k!\}\backslash sum\_\{i=0\}^\{k-1\}\{k!\backslash over\; i!\backslash times(k-i)!\}2^i[\{x^i\backslash over\; i!\}]\backslash hat\; f\_\{n-1\}(x)$f^​n​(x)=∑k=0+∞​k!xk​∑i=0k−1​i!×(k−i)!k!​2i[i!xi​]f^​n−1​(x)

$={\sum }_{k=0}^{+\infty }{x}^k{\sum }_{i=0}^{k-1}\frac{1}{(k-i)!}\times \frac{2^i}{i!}\left[\frac{x^i}{i!}\right]{\widehat{f}}_{n-1}\left(x\right)=\backslash sum\_\{k=0\}^\{+\backslash infty\}x^k\backslash sum\_\{i=0\}^\{k-1\}\{1\backslash over\; (k-i)!\}\backslash times\{2^i\backslash over\; i!\}[\{x^i\backslash over\; i!\}]\backslash hat\; f\_\{n-1\}(x)$=∑k=0+∞​xk∑i=0k−1​(k−i)!1​×i!2i​[i!xi​]f^​n−1​(x)

$={\sum }_{k=0}^{+\infty }{x}^k{\sum }_{i=0}^{k-1}\frac{1}{(k-i)!}\left[x^i\right]{\widehat{f}}_{n-1}\left(2x\right)=\backslash sum\_\{k=0\}^\{+\backslash infty\}x^k\backslash sum\_\{i=0\}^\{k-1\}\{1\backslash over\; (k-i)!\}[x^i]\backslash hat\; f\_\{n-1\}(2x)$=∑k=0+∞​xk∑i=0k−1​(k−i)!1​[xi]f^​n−1​(2x)

$={\sum }_{i=0}^{+\infty }{x}^i\left[x^i\right]{\widehat{f}}_{n-1}\left(2x\right){\sum }_{k=i+1}^{+\infty }{x}^{k-i}\frac{1}{(k-i)!}=\backslash sum\_\{i=0\}^\{+\backslash infty\}x^i[x^i]\backslash hat\; f\_\{n-1\}(2x)\backslash sum\_\{k=i+1\}^\{+\backslash infty\}x^\{k-i\}\{1\backslash over\; (k-i)!\}$=∑i=0+∞​xi[xi]f^​n−1​(2x)∑k=i+1+∞​xk−i(k−i)!1​

$={\sum }_{i=0}^{+\infty }{x}^i\left[x^i\right]{\widehat{f}}_{n-1}\left(2x\right){\sum }_{k=1}^{+\infty }\frac{x^k}{k!}=\backslash sum\_\{i=0\}^\{+\backslash infty\}x^i[x^i]\backslash hat\; f\_\{n-1\}(2x)\backslash sum\_\{k=1\}^\{+\backslash infty\}\{x^k\backslash over\; k!\}$=∑i=0+∞​xi[xi]f^​n−1​(2x)∑k=1+∞​k!xk​

$=(e^x-1){\sum }_{i=0}^{+\infty }{x}^i\left[x^i\right]{\widehat{f}}_{n-1}\left(2x\right)=(e^x-1)\backslash sum\_\{i=0\}^\{+\backslash infty\}x^i[x^i]\backslash hat\; f\_\{n-1\}(2x)$=(ex−1)∑i=0+∞​xi[xi]f^​n−1​(2x)

$=(e^x-1){\widehat{f}}_{n-1}\left(2x\right)=(e^x-1)\backslash hat\; f\_\{n-1\}(2x)$=(ex−1)f^​n−1​(2x)

即，${\widehat{f}}_n\left(x\right)=(\exp x-1){\widehat{f}}_{n-1}\left(2x\right)\backslash hat\; f\_n(x)=(\backslash exp\; x-1)\backslash hat\; f\_\{n-1\}(2x)$f^​n​(x)=(expx−1)f^​n−1​(2x)。

边界 ${\widehat{f}}_0\left(x\right)=1\backslash hat\; f\_0(x)=1$f^​0​(x)=1。

展开来，我们有

${\widehat{f}}_n\left(x\right)={\prod }_{i=0}^{n-1}(e^{2^{i}x}-1)\backslash hat\; f\_n(x)=\backslash prod\_\{i=0\}^\{n-1\}(e^\{2^ix\}-1)$f^​n​(x)=∏i=0n−1​(e2ix−1)

而我们要求的，就是

$ans={\sum }_{i=0}^k\left(\frac{k}{i}\right)\left[\frac{x^i}{i!}\right]{\widehat{f}}_n\left(x\right)=k!{\sum }_{i=0}^k\frac{\left[x^i\right]{\widehat{f}}_n\left(x\right)}{(k-i)!}ans=\backslash sum\_\{i=0\}^\{k\}\backslash binom\; ki[\{x^i\backslash over\; i!\}]\backslash hat\; f\_n(x)=k!\backslash sum\_\{i=0\}^\{k\}\{[x^i]\backslash hat\; f\_n(x)\backslash over(k-i)!\}$ans=∑i=0k​(ik​)[i!xi​]f^​n​(x)=k!∑i=0k​(k−i)![xi]f^​n​(x)​

因此只要能卷出 $f_n\left(x\right)mod{x}^{k+1}f\_n(x)\; \backslash bmod\; x^\{k+1\}$fn​(x)modxk+1 就可得答案。

由展开式，我们有：

${\widehat{f}}_{2n}\left(x\right)={\widehat{f}}_n\left(x\right)\times {\widehat{f}}_n\left(2^{n}x\right)\backslash hat\; f\_\{2n\}(x)=\backslash hat\; f\_n(x)\backslash times\backslash hat\; f\_n(2^nx)$f^​2n​(x)=f^​n​(x)×f^​n​(2nx)

又有

${\widehat{f}}_{2n+1}\left(x\right)={\widehat{f}}_{2n}\left(x\right)\times (e^{2^{2n}x}-1)\backslash hat\; f\_\{2n+1\}(x)=\backslash hat\; f\_\{2n\}(x)\backslash times(e^\{2^\{2n\}x\}-1)$f^​2n+1​(x)=f^​2n​(x)×(e22nx−1)

于是可以倍增或者递归卷出 ${\widehat{f}}_n\left(x\right)\backslash hat\; f\_n(x)$f^​n​(x)。我采用了后者。

时间复杂度：

$T\left(n\right)=T\left(\frac{n}{2}\right)+O(n\log n)=O(n\log n)T(n)=T(\backslash frac\; n2)+O(n\backslash log\; n)=O(n\backslash log\; n)$T(n)=T(2n​)+O(nlogn)=O(nlogn)

Code

模数 $10000000071000000007$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

总结

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

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

这确实算是一个教训吧。