P17284 「IXOI R2」想不出来
题目背景
如你所见，出题人又想不出来题目名字。
[头大].jpg
题目描述
给定长度为 的序列 。
你有一个长度为 的序列 ，初始 。
定义一次操作为：选择 ，将序列中 位置和 位置上的数移动到 位置上。
形式化地，每次操作可以视为，令：
- ；
- ；
- 。
特别地，如果 或 位置不存在，则不在 或 位置进行操作。
我们称一个序列 是愚蠢的，当且仅当它可以通过任意次操作由初始序列 生成。
我们称两个序列 是本质不同的，当且仅当 。
定义序列 的权值为：
现在请求出所有本质不同的愚蠢的序列 的权值和并输出答案对 取模后的结果。
这里认为 。
输入格式
输入共两行，第一行一个正整数 。第二行一个长度为 的数组 。
输出格式
输出一个数，表示所有本质不同的愚蠢的序列 的权值和并输出答案对 取模后的结果。
输入输出样例 #1
输入 #1
6
2 3 1 5 6 6输出 #1
648718输入输出样例 #2
输入 #2
5
17 43 2 6 7输出 #2
207004448说明/提示
本题采用捆绑测试。
| Subtask | 特殊性质 | 分值 | |
|---|---|---|---|
| 无 | |||
| 无 | |||
| 无 |
对于所有数据，保证：
保证 。
性质挖掘
我们先不去想这个序列是怎么一步步变过来的，而是直接去观察最终生成的序列（也就是合法的 ），看看它必定满足什么条件。
结论1：只要出现一个大于 1 的数，它的左边和右边一定是 0。
如果某个位置的数字 ，说明它一定“吸收”过两边的数字。想象一下它最后一次吸收数字的场景：它把左边 和右边 抽干了，两边变成了 0。在这之后，因为这是“最后一次”涉及这三个位置的操作，所以两边的 0 就再也没有被改变过。
结论2：在遇到连续的 1 时，前面这段前缀的 之和，必须正好等于这段前缀的长度，因为数字没有发生过跨越。
如果序列里出现两个挨着的 1（即 ），这意味着什么？意味着这两个位置从来没有被操作过，也从来没有被当成养分吸走。它们就像绝缘体一样，把整个序列从这里切断了，左边的数字永远过不去右边，右边的也过不来。
设计动态规划状态
有了上面的性质，我们就可以从左到右去填数字了。由于我们要统计的是不同 序列的权值之和（权值是 ），我们需要记录三个信息：
- 当前填到了第几个位置（阶段
i）。 - 当前填进去的数字总和是多少（限制条件
j，总和最后必须是 ）。 - 当前这个位置填的数字状态是什么，因为我们需要判断连续的 0 或者 1（状态
0/1/2）。
我们设计状态 dp[j][0/1/2]（这里省略第一维 i，直接用滚动数组）：
dp[j][0]：当前位置填了 0，且当前前缀和为j的权值和。dp[j][1]：当前位置填了 1，且当前前缀和为j的权值和。dp[j][2]：当前位置填了大于 1 的数，且当前前缀和为j的权值和。
理清状态转移
现在假设我们要计算第 i 个位置的转移，我们用 nxt 数组表示推导出的新一层状态。
当前位置想填 0
填 0 是没有任何顾虑的，无论前一个位置是 0、1 还是大于 1 都可以。而且 0 对总和 也没有增加，对权值（）也没有影响。nxt[j][0] = dp[j][0] + dp[j][1] + dp[j][2]当前位置想填 1
这里要分情况：前一个位置是 0：没有触发“连续的 1”的墙壁限制，很自由。前缀和增加 1。
nxt[j + 1][1] += dp[j][0] * x[i]前一个位置是 1：触发了墙壁性质！这要求当前的前缀和必须完美匹配当前长度。也就是说，当前这个状态的 必须等于 。
nxt[i][1] += dp[i - 1][1] * x[i]
当前位置想填大于 1 的数（假设填了 k，且 k >= 2）
根据我们的第一个结论，大于 1 的数左边必须是 0！所以上一个状态只能是dp[...][0]。
我们要加上 ，所以前一个状态的 需要减去 。nxt[j][2] = 求和(dp[j - k][0] * x[i]^k) // 这里的 k 取 2, 3, 4...
代数优化
上面计算 nxt[j][2] 的时候，需要枚举一个 ，这会导致时间复杂度变成 。但是我们可以把式子展开看：
当总和是 j 时，我们需要求：dp[j-2][0] * x[i]^2 + dp[j-3][0] * x[i]^3 + ...
当总和推进到 j+1 时，我们需要求：dp[j-1][0] * x[i]^2 + dp[j-2][0] * x[i]^3 + dp[j-3][0] * x[i]^4 + ...
仔细观察上下两行，你发现规律了吗？
下面一行的后面一大串，正好是上面一行整体乘上一个 x[i]！
所以我们可以维护一个变量 cursum，从小到大枚举 j 的时候：cursum = cursum * x[i] + dp[j-2][0] * x[i]^2
直接省掉了一层循环，复杂度降到了 。
代码实现
#include<bits/stdc++.h>
using namespace std;
#define int long long
int32_t MeloAPIOFe;
int n;
int x[8005];
int dp[8005][3];
int nxt[8005][3];
const int mod = 1e9 + 7;
template<typename T>
void read(T &val) {
val = 0;
char c = getchar();
short f = 1;
while (c < '0' || c > '9') {
if (c == '-') f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
val = (val << 1) + (val << 3) + (c ^ 48);
c = getchar();
}
val *= f;
}
template <typename T, typename... Args>
void read(T &val, Args &...args) {
read(val), read(args...);
}
void write(int val) {
static int sta[35];
int top = 0;
do {
sta[top++] = val % 10;
val /= 10;
} while (val);
while (top) putchar(sta[--top] + '0');
}
void solve() {
read(n);
for (int i = 1; i <= n; ++i) {
read(x[i]);
}
// 初始状态，长度为0，和为0，默认算在状态0上
dp[0][0] = 1;
for (int i = 1; i <= n; ++i) {
memset(nxt, 0, sizeof(nxt));
// 转移状态0：当前填0
for (int j = 0; j <= n; ++j) {
nxt[j][0] = (dp[j][0] + dp[j][1] + dp[j][2]) % mod;
}
// 转移状态1：当前填1
for (int j = 0; j < n; ++j) {
// 前一位是0的转移
nxt[j + 1][1] = (nxt[j + 1][1] + dp[j][0] * x[i]) % mod;
}
// 前一位是1的转移，强制限制前缀和等于i
nxt[i][1] = (nxt[i][1] + dp[i - 1][1] * x[i] % mod) % mod;
// 转移状态2：当前填大于1的数字
int cursum = 0;
int pw = x[i] * x[i] % mod;
for (int j = 2; j <= n; ++j) {
// 利用前缀和的性质进行O(1)递推
cursum = (cursum * x[i] % mod + dp[j - 2][0] * pw % mod) % mod;
nxt[j][2] = cursum;
}
// 滚动数组覆盖
memcpy(dp, nxt, sizeof(dp));
}
// 最终答案要求总和为n，把三种结尾情况加起来
int ans = (dp[n][0] + dp[n][1] + dp[n][2]) % mod;
write(ans);
putchar('\n');
}
signed main() {
solve();
return 0;
}