好玩题。
对于一个排列 \(p\)，进行 \(k\) 轮冒泡，记 \(v_i = \sum_{j < i} [p_j < p_i]\)，给定 \(v_i\)，部分值不确定，求合法的 \(p\) 的个数。
- \(p\) 由 \(v\) 唯一确定。
考虑一个个加数字进去，每次可以判断加入数字与前面数字的相对大小，于是可以确定原排列。
只用研究 \(v\)，不用研究 \(p\)。
- 一轮冒泡形如：整体前移 \(1\) 位，减一，对 \(0\) 取 \(\max\)。
相邻两项会交换等价于后一项的 \(v\) 不为 \(0\)，否则一定交换，对应 \(v\) 减一。
于是最后的 \(v\) 是原来的 \(v\) 左移 \(k\) 位，减 \(k\)，对 \(0\) 取 \(\max\)。
- 不合法的情况只有：最后 \(k\) 项不为 \(0\)，\(v_i \geq i\)。
其余情况一定合法。
为 \(-1\) 时，有 \(i\) 种互不干涉的选择；为 \(0\) 时，有 \(\min\{i, k+1\}\) 种选择；否则选择唯一。
题目不难，记录下来只是想反思：为什么自己没有想到？
我想到了直接去看 \(v\) 的特征，发现了前移的特征，但是因为多个 \(v\) 会得到一个结果，没有继续往后想。
很应该想到的是，研究 \(p\)，最后仍然要转到 \(v\) 上，因此不如研究 \(v\)；至于后面的发现，均较为自然。
没脑子了，what should I do?
#include <bits/stdc++.h>
const int mod = 998244353;
int solve() {
int n, k, ans = 1; scanf("%d %d", &n, &k);
std::vector<int> a(n);
for (auto &v : a) scanf("%d", &v);
for (int i = n - k; i < n; i++) if (a[i] && a[i] != -1) return 0;
for (int i = 0; i < n; i++) if (a[i] > i) return 0;
for (int i = 0; i < k; i++) ans = 1ll * ans * (i + 1) % mod;
for (int i = 0; i < n - k; i++) {
if (a[i] == -1) ans = 1ll * ans * (i + k + 1) % mod;
else if (a[i] == 0) ans = 1ll * ans * (k + 1) % mod;
}
return ans;
}
int main() {
int t; scanf("%d", &t); while (t--) {
printf("%d\n", solve());
}
}