CF2140E

· · 题解

然后你考虑把 1 的意义改写为 $\le t(t\in [1,m])$，2 的意义是 $> t$，这样如果某个起始状态的 dp 值是 1，那么意味着这个状态起手，答案会 $\le t$。所以对于一个 $t$，能让答案 $\le t$ 的方案数是： $$\sum_{bit}[dp_{n,bit,0}=1]t^{n-\operatorname{popcount}(bit)}(m-t)^{\operatorname{popcount}(bit)}$$ 后面的幂次是在把 1 替换为 $\le t$ 的数，2 替换为 $>t$ 的数。 这个式子可以预处理 $num_i=\sum_{bit}[dp_{n,bit,0}=1][\operatorname{popcount}(bit)=i]$ 后 $O(n)$ 计算。对所有 $t\in[1,m]$ 都算一遍（$t=m$ 要特殊处理，应有 $m^n$ 种方案）后差分就能得到答案恰好等于 $t$ 的方案数。然后乘上 $t$ 求和输出即可。