容易发现序列必须是单谷序列，否则必然不满足性质。
考虑枚举谷的位置为 ，则有这样一个经典的刻画单谷序列的方式：
- 执行若干次下面的操作：
- 把序列 中所有元素的值都增加 。
- 选择一个位置 ：
- 若 ，则将 的值分别增加 。
- 若 ，则将 的值分别增加 。
容易证明上述刻画方式和全部单谷序列组成了双射关系。
考虑固定 的值，则问题可以被转化成 个数跑计数的完全背包求方案数。直接背包时间复杂度是 的肯定不可行。注意到从左往右扫描 端点时，完全背包元素的变化量很小，因此容易想到使用回滚背包将时间复杂度优化到 。
:::success[代码实现]
namespace lowspeed_song {
inline void init() {
}
int f[N];
inline void sol() {
int n, m; cin >> n >> m;
f[0] = 1;
for (int i = 1; i < n && i * (i + 1) / 2 <= m; ++i)
for (int j = i * (i + 1) / 2; j <= m; ++j) f[j] = (f[j] + f[j - i * (i + 1) / 2]) % mod;
for (int j = n; j <= m; ++j) f[j] = (f[j] + f[j - n]) % mod;
int res = 0;
for (int i = 1; i <= n; ++i) {
if (i * (i - 1) / 2 <= m) res = (res + f[m - i * (i - 1) / 2]) % mod;
if ((n - i) * (n - i + 1) / 2 <= m) {
for (int j = m; j >= (n - i) * (n - i + 1) / 2; --j) f[j] = (f[j] + mod - f[j - (n - i) * (n - i + 1) / 2]) % mod;
} if (i * (i + 1) / 2 <= m) {
for (int j = i * (i + 1) / 2; j <= m; ++j) f[j] = (f[j] + f[j - i * (i + 1) / 2]) % mod;
}
} cout << res << '\n';
}
} // namespace lowspeed_song
喜欢的话，留下你的评论吧～