[NOIP2021 T2] 数列题解

这个题的核心思想就是，从小到达向序列中填数，每次找当前枚举的数填了多少，然后考虑把它加到

S

中的进位问题。

我们用

f_{i,j,k,l}

表示状态：

$i$ 表示向序列中填完了 $1$ 到 $i-1$ ，接下来要填 $i$ 这个数，也就是我们讨论了 $S$ 从低到高的第 $i$ 位。
$j$ 表示序列中有了 $j$ 个数。
$k$ 表示 $S$ 中进完位的部分有 $k$ 个 $1$ 。
$l$ 表示最后一位还没进上去位的部分：比如说 $101111$ 这个数，最高的 $2$ 位的 $l$ 就是 $2$ （对应进位后的 $10$ ，最高的 $3$ 位的 $l$ 就是 $5$ （对应展开后的101），以此类推。

我们每次枚举一个已经填好的状态

(i,j,k,l)

，然后再枚举一个

p

表示我们填多少个

i

到序列里面。接下来讨论转移：

$i$ 应该转移到 $i+1$ ，因为我们要考虑下一位。
$j$ 应该转移到 $j+p$ ，因为我们新加了 $p$ 个数。
然后是 $k$ ，先考虑 $l$ 的变化，此时我们的 $l$ 就变成了 $l+p$ 。而我们接下来要填下一位了，所以我们要把第 $i$ 位进上去，看是否保留 $1$ 。这个过程相当于二进制展开，如果最后一位是 $1$ ，也就是说 $l+p$ 是奇数，那么我们就让这一位是 $1$ ，也就是让 $k$ 增加 $1$ 。因此 $k$ 会不会增加取决于 $l+p$ 是奇数还是偶数。因此 $k$ 转移到 $k+(l+p)\%2$ 。
最后是 $l$ ，我们需要更新进位后还没有进位的部分，因此我们令 $l$ 转移到 $(l+p)/2$ 。

举个例子，如果

S

当前是

3-10001

（“

-

”前面是没进位的部分），如果我们填入

2

个数，那么我们就让这个

3

变成

5

，然后再进位，此时

S

就变成了

2-110001

。

然后我们发现，我们需要计算填入后的数的权值以及序列的数目，因为新序列的权值和就是原序列的权值乘上新序列的权值再乘上新序列的数目。

f_{i+1,j+p,k+(l+p)\%2,(l+p)/2}

加上

k

倍的

f_{i,j,k,l}

来转移。

首先权值是

v_i

的

k

次方，然后新序列的种类数需要用到插板法。问题转化为用

j

个板子分开

p

个数的方案，中间可以空。所以这部分的答案就是

j+p \choose p

。所以最终的式子就是：

f_{i+1,j+p,k+(l+p)\%2,(l+p)/2}+=f_{i,j,k,l}*v_j^k*{j+p \choose p}

。

我们统计完以后，枚举所有前两位为

n,m

的状态，此时

l

的贡献是

popcount(l)

，即

1

的个数就是

k+popcount(l)

。如果这个数不大于

m

（

m

就是

1

的最大个数），那它就是合法方案，我们把它加进

ans

里面。

这样我们就把这个题做完了。

文章操作