---

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

---

总结

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

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

这确实算是一个教训吧。