P7961 数列 题解

• 对模拟的过程不敏感，对范围的数字不敏感

• 手玩是发现规律的好方式

• 计数 dp 以及一众计数题是明显短板，需要加紧突破。

样例解释已经较为明显地提示了这道题的大致做法。对于计数题，有动归与组合数学两种方法。但这道题并不是很能推式子，所以采用动态规划。

我们需要统计 (0) 到 (m) 每个元素的个数，所以要有一维记录当前推到第几个元素。

答案与整数 (S) 有较大关联，我们需要一维记录当前递推到 (S) 第几位。

发现根据上面两维无法表示 (1) 的 数量不超过 (k) 个，于是要再开一维表示当前 (S) 有几个 (1)。

但是由于每个点可以选多次，所以我们只凭这些，最终 (1) 的个数还是无法确定。

我们得到了一个半成品数组，(dp_{i,j,k}) 表示当前推到第 (i) 个元素，推到第 (j) 位，当前有 (k) 个 (1) 的答案。

如果你推到这里卡住了，没有关系。你需要的是查看一众 NOI 拿金游记并睡一觉。

试着根据这个半成品数组设计转移方程，我们发现由于有 (1) 的个数存在，并不是很好推这个状态是由哪些状态转移而来得到，但我们只需枚举当前第 (i) 个元素选了几个，就可以推出这个状态对后面状态的贡献。通过枚举选了 (t) 个，我们可以得出当前的位是 (0) 还是 (1)，但是尽管同样是 (1)，选 (1) 个和选 (3) 个还是有很大的不同的。这会影响下一位的值，也许还会影响下下位的。

发现实际上，这个影响取决于进位的多少。所以我们还需要一维，表示当前一位要向后进多少的值。

成品数组产生了：(dp_{i,j,k,w}) 表示当前推到第 (i) 个元素，推到第 (j) 位，当前有 (k) 个 (1) ，且要向下一位进 (w) 的值。显然， (w) 最大就是 (n)，因为当前元素最多选 (n) 个。

贡献是多少？(dp_{i,j,k,w}) 实际上就是一种方案的权值乘上这种方案产生的序列个数。显然，现有的权值要乘上 (p_i)。产生的序列个数就是在选剩的格子里（共 (n-j) 个）选 (t) 个填上的方案乘上原来的方案。根据结合律可得：

f[i + 1][j + t][w + ((t + p) % 2)][(t + p) / 2] += ((((f[i][j][w][p] * qp[i][t]) % mod) * C[n - j][t]) % mod);

最后统计答案时要注意，第 (n) 位的进位也要加以判断。实际上就是求进位数的 popcount ，如果这个和原来的 (k) 加起来不大于题目要求才可被统计。