同见于我的洛谷博客 Update dp 式没有使用函数形式，否则会与生成函数混淆，请注意。 前言 手推了好久柿子才推出来，结果最后一步不会，最后看了题解才知道是倍增。 所以，这算一个教训吧。 思路 以下默认 b0=0b_0=0b0=0。 首先 n>kn>kn>k 显然无解，原理是每次 nnn 加一必然多至少一位值为 111。 我们设 fn,kf_{n,k}fn,k 为恰好占用了 kkk 个二进制位时长度为 nnn 的序列的方案数。特别的，n>kn>kn>k 时 fn,k=0f_{n,k}=0fn,k=0。 由定义，我们有 ans=∑i=0k(...
