Count Multiset

Arc221H-Link

Solution

第一步，对于 multiset 计数，我们将其转换成 对于单调不降数列计数。

这时看起来对于单调不降数列计数已经有较好的性质了，我们也可以得到如下的 \(\mathcal{O(n^3)}\) 的 dp。

对于每个 \(t\),更新 dp 数组：\(\text{dp}_i(x)=\sum_{j=1}^{m} \text{dp}_{i-j}(x-tj)\)，如果你了解背包问题的话，这个相当于对所有整数做一个完全背包。

复杂度我并不会优化，所以根据题解有了如下思路。

---

第二步，对于单调不降数列计数可以通过差分转换成一个非负整数数列。

当然对于别的一些单调不降数列计数的话，差分会较大影响原数列的性质，所以这个并不是一个常见套路。

现在问题转化成，对于 \(k\leq n\) 满足 \(\sum_{i=1}^{k}a_i\times(k-i+1)=n , a_1\not = 0\) 且没有 \(m\) 个连续的 \(0\) 的非负整数数列个数。

这样一个显然的 dp 转移出来了。

\(\text{dp}_{i}(n)=\sum_{j=0}\sum_{k=i-m}\text{dp}_{k}(n-j\times i)\)

相当是把原属列 reverse 以下，然后 dp。

你只需要保证最后一次不是从 \(0\) 转移的即可。

\(j\) 的总枚举量是 \(n\ln n\)，可以对 \(i\) 为前缀和，总复杂度 \(\mathcal{O(n^2\ln n)}\)