题目题解

问题理解

初始数组为空。每次操作可以选择 $s \ge 1$ 和 $1 \le r \le s$，将

$$[r, r+1, \dots, s, 1, 2, \dots, r-1]$$

追加到数组末尾。给定 $n$ 和 $m$ 条限制 $a_i \neq x$，统计所有长度为 $n$ 且满足限制的可构造数组的个数，对 $998244353$ 取模。

---

第一步：数组的结构

每次追加的是一个 $1$ 到 $s$ 的循环移位排列。
最终数组由若干段这样的排列拼接而成，每段的数值范围是 $[1, s]$。

---

第二步：重复计数问题

同一个数组可能有多种拆分方式。例如 $[1,2,1]$ 可以拆成 $[1,2] + [1]$ 或 $[1] + [2,1]$。
这种重复源于：当先加一个长度为 $x$ 的恒等排列 $[1,2,\dots,x]$，再加一个长度为 $y$ 的恒等排列 $[1,2,\dots,y]$（$x > y$）时，也可以视为先加长度为 $y$ 的排列再加一个长度为 $x$ 的循环移位。

为了避免重复，我们规定：不允许在恒等排列后面紧接着一个以 $y+1$ 开头的循环移位。
在 DP 状态中，我们记录最后一个排列是否是恒等排列及其长度。

---

第三步：动态规划状态

设：

• $dp(i, j)$ 表示从位置 $i$ 开始到末尾，且 $a_i = j$ 的方案数。
• $tot(i) = \sum_{j=1}^n dp(i, j)$ 表示从位置 $i$ 开始的总方案数。
• $suff(i, j)$ 表示从位置 $i$ 开始，准备放置以 $j$ 开头的序列（不检查限制）的方案数。

---

第四步：预处理 chain(i, j)

chain(i, j) 表示从位置 $i$ 开始，连续放置 $j, j+1, j+2, \dots$ 且不违反限制的最大长度。
递推：

$$\text{chain}(i, j) = \begin{cases} 0 & \text{if } a_i \neq j \text{ 是限制}, \\ 1 + \text{chain}(i+1, j+1) & \text{otherwise}. \end{cases} $$

---

第五步：计算 suff(i, j)

suff(i, j) 表示从位置 $i$ 开始，放置一个以 $j$ 开头的循环移位排列后，剩余部分的所有方案数之和。

若固定 $j$，我们考虑所有可能的起始位置 $x \ge i$，使得我们可以从 $x$ 开始连续放置 $1,2,\dots,j-1$（共 $j-1$ 个连续数）。这等价于 $\text{chain}(x, 1) \ge j-1$。
此时，位置 $x + j - 1$ 之后的部分可以任意填充，方案数为 $tot(x + j - 1)$。

因此：

$$\text{suff}(i, j) = \sum_{x = i}^{n} [\text{chain}(x, 1) \ge j-1] \cdot tot(x + j - 1). $$

---

第六步：转移方程

1. $j = 1$ 的情况（添加一个恒等排列）：
   我们尝试在位置 $i$ 开始一个长度为 $len$ 的恒等排列 $[1,2,\dots,len]$。
   方案数为 $tot(i + len)$，但要减去 $dp(i + len, len + 1)$ 以避免与另一种拆分方式重复。

   $$dp(i, 1) = \sum_{len \ge 1} \left( tot(i + len) - dp(i + len, len + 1) \right). $$

2. $j > 1$ 的情况：
   此时 $a_i$ 必须等于 $j$。我们从 $i+1$ 开始，可以放置任意以 $j+1$ 开头的序列，但必须保证从 $i$ 开始的连续 $j$ 个位置可用。
   这恰好是 suff(i+1, j) 减去那些因 $a_i \neq j$ 限制而不可用的部分，即：

   $$dp(i, j) = \text{suff}(i+1, j) - \text{suff}(i+1 + \text{chain}(i, j), j). $$

---

第七步：递推顺序

从 $i = n$ 向下递推到 $i = 1$：

• 先计算 chain 数组。
• 计算 suff(i, j) 需要知道 $tot$ 在更大索引的值，因此我们从大到小计算。
• 每步更新 $tot(i)$ 和 suff(i, j)。

---

第八步：最终答案

$tot(1)$ 即为所有合法方案数。

---

时间复杂度

• 预处理 chain：$O(n^2)$。
• 计算 suff 和 DP：$O(n^2)$。
• 总复杂度 $O(n^2 + m)$，满足 $n \le 5000$。

---

代码实现

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;
const int MAXN = 5005;

short chain[MAXN][MAXN];
int ssum[MAXN][MAXN];
int tot[MAXN];
bool ban[MAXN][MAXN];
int c1[MAXN];

void solve() {
    int n, k;
    cin >> n >> k;

    memset(ban, 0, sizeof(ban));
    memset(chain, 0, sizeof(chain));
    memset(ssum, 0, sizeof(ssum));
    memset(tot, 0, sizeof(tot));

    for (int i = 0; i < k; i++) {
        int x, y;
        cin >> x >> y;
        ban[x][y] = 1;
    }

    tot[n + 1] = 1;

    // chain
    for (int i = n; i >= 1; i--) {
        for (int j = n; j >= 1; j--) {
            if (ban[i][j]) {
                chain[i][j] = 0;
            } else {
                chain[i][j] = 1 + chain[i + 1][j + 1];
                if (chain[i][j] > n - i + 1) chain[i][j] = n - i + 1;
                if (chain[i][j] > n - j + 1) chain[i][j] = n - j + 1;
            }
        }
        c1[i] = chain[i][1];
    }

    // DP
    for (int i = n; i >= 1; i--) {
        // ssum
        int* ssum_i = ssum[i];
        int* ssum_ip1 = ssum[i + 1];
        for (int j = 1; j <= n - i + 1; j++) {
            ssum_i[j] = ssum_ip1[j];
            if (c1[i] >= j) {
                ssum_i[j] = (ssum_i[j] + tot[i + j]) % MOD;
            }
        }

        // j = 0 (恒等排列)
        int maxlen = c1[i];
        for (int len = 1; len <= maxlen; len++) {
            tot[i] = (tot[i] + tot[i + len]) % MOD;
            int nxt = i + len;
            int jj = len + 1;
            if (nxt <= n + 1 && jj <= n + 1) {
                int sub = ssum[nxt + 1][jj];
                int nxt2 = nxt + 1 + chain[nxt][jj];
                if (nxt2 <= n + 1) {
                    sub = (sub - ssum[nxt2][jj] + MOD) % MOD;
                }
                tot[i] = (tot[i] - sub + MOD) % MOD;
            }
        }

        // j >= 1
        for (int j = 1; j <= n - i + 1; j++) {
            if (chain[i][j] == 0) continue;
            int val = ssum[i + 1][j];
            int nxt = i + 1 + chain[i][j];
            if (nxt <= n + 1) {
                val = (val - ssum[nxt][j] + MOD) % MOD;
            }
            tot[i] = (tot[i] + val) % MOD;
        }
    }

    cout << tot[1] << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

---

总结

本题的关键在于：

1. 识别重复计数问题，引入状态记录最后一个排列的类型。
2. 预处理 chain 数组快速判断连续放置的可行性。
3. 使用 suff 辅助数组加速转移，将复杂度优化到 $O(n^2)$。