AtCoder Beginner Contest 468 题解

for-each2026年8月18日大约 18 分钟

AtCoder Beginner Contest 468 题解

项目	内容
比赛时间	2026-07-25
比赛链接	https://atcoder.jp/contests/abc468
题目数量	A–G 共 7 题

比赛概览

本场 ABC468 整体难度中等偏上：A–C 是送分题（直接模拟、枚举），D 题考察"至多改一个字符成为回文"的刻画与中心扩展计数，E 题是前缀和 + 调和级数的经典求和交换，F 题是带状态约简的动态规划（并等价于 LIS），G 题则是较有区分度的组合计数题（利用连续块的独立性把答案写成若干子问题的乘积）。值得重点掌握的是 D 的"至多一个错配对称对"的刻画、E 的交换求和顺序技巧，以及 F、G 的状态设计与问题分解思想。

A - Maximal Value

题目链接：https://atcoder.jp/contests/abc468/tasks/abc468_a

题目大意

给定长度为 $N$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$ ，统计满足 $A_i < A_{i+1} > A_{i+2}$ 的下标 $i$ （ $1\le i\le N-2$ ）的个数。约束： $3\le N\le 100$ 。

思路

题目定义的条件就是一个"局部峰值"： $A_{i+1}$ 严格大于左右邻居。由于 $N$ 很小，直接对每个 $i=1,2,\ldots,N-2$ 逐一检查即可。

注意边界：

循环只走到 $i=N-2$ （即 0-based 下 $i+2 < N$ ），不能越界；
不等式都是严格的（< 和 >），相等不算数。

正确性显然：每个满足条件的三元组恰被检查一次，累加即为答案。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    int ans = 0;
    for (int i = 0; i + 2 < n; i++) {
        if (a[i] < a[i + 1] && a[i + 1] > a[i + 2]) ans++;
    }
    cout << ans << '\n';
    return 0;
}

复杂度分析

时间复杂度： $O(N)$
空间复杂度： $O(N)$ （或 $O(1)$ 若边读边判断）

B - Corridor Watch

题目链接：https://atcoder.jp/contests/abc468/tasks/abc468_b

题目大意

有 $M$ 个从左到右排列的格子（编号 $1\sim M$ ），其中字符串 $S_i=$ G 的格子上站着一名守卫，其余为 .。一个格子 $x$ 被称为"被监视"，当且仅当存在某个守卫所在的格子 $i$ 满足 $|x-i|\le D$ 。求不被监视的格子数量。约束： $0\le D < M\le 100$ 。

思路

一个格子 $x$ 不被监视，等价于它与所有守卫格子的距离都大于 $D$ 。

最直接的想法是枚举每个格子 $x$ ，再枚举所有守卫格子判断是否有点距 $\le D$ ，复杂度 $O(M^2)$ ，在本数据范围下完全可行（这也是官方题解的做法）。

我们还可以做得更好，用两次线性扫描：

设 dist[x] 为格子 $x$ 到最近的守卫的距离（若左右都没有守卫则为 $+\infty$ ）。
从左到右扫描一遍，维护"最近的左侧守卫位置"，得到每个格子到左侧最近守卫的距离；
从右到左扫描一遍，维护"最近的右侧守卫位置"，得到每个格子到右侧最近守卫的距离，并取两者最小值。

这样 dist[x] = min(左距离, 右距离) 就是到最近守卫的距离。若 dist[x] > D 则不被监视。该做法可进一步用于约束放宽到 $N\le 5\times 10^5$ 的加强版。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int m, d;
    string s;
    cin >> m >> d >> s;
    const int INF = 1e9;
    vector<int> dist(m, INF);
    int last = -1;
    for (int i = 0; i < m; i++) {            // 从左到右：最近左侧守卫
        if (s[i] == 'G') last = i;
        if (last != -1) dist[i] = min(dist[i], i - last);
    }
    last = -1;
    for (int i = m - 1; i >= 0; i--) {       // 从右到左：最近右侧守卫
        if (s[i] == 'G') last = i;
        if (last != -1) dist[i] = min(dist[i], last - i);
    }
    int ans = 0;
    for (int i = 0; i < m; i++) {
        if (dist[i] > d) ans++;
    }
    cout << ans << '\n';
    return 0;
}

复杂度分析

时间复杂度： $O(M)$ （朴素枚举为 $O(M^2)$ ，同样可过）
空间复杂度： $O(M)$

C - Between P and Q

题目链接：https://atcoder.jp/contests/abc468/tasks/abc468_c

题目大意

给定 $N$ 和两个排列 $P=(P_1,\ldots,P_N)$ 、 $Q=(Q_1,\ldots,Q_N)$ ，求有多少个 $(1,2,\ldots,N)$ 的排列 $a$ 满足： $P$ 在字典序上严格小于 $a$ ，且 $a$ 在字典序上严格小于 $Q$ 。约束： $N\le 10$ 。

思路

$N\le 10$ 时共有 $N!\le 10! = 3628800$ 个排列，完全可以直接枚举全部排列并逐一判断是否满足 $P<a<Q$ 。

在 C++ 中可以用 next_permutation 从 $(1,2,\ldots,N)$ 开始无重复地枚举所有排列；对两个等长序列的比较，vector 自带的 < 运算符就是按字典序比较的，直接使用即可。在 Python 中则用 itertools.permutations。

需要注意的易错点：

题目要求的是严格大于 $P$ 、严格小于 $Q$ ，即 $P<a$ 且 $a<Q$ ，不要把 $a$ 与 $P$ 或 $Q$ 本身算进去；
若 $P\ge Q$ ，答案自然为 $0$ ，枚举法会直接给出正确结果。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> p(n), q(n);
    for (int &x : p) cin >> x;
    for (int &x : q) cin >> x;
    vector<int> a(n);
    iota(a.begin(), a.end(), 1);
    int ans = 0;
    do {
        if (p < a && a < q) ans++;
    } while (next_permutation(a.begin(), a.end()));
    cout << ans << '\n';
    return 0;
}

from itertools import permutations

n = int(input())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
ans = 0
for a in permutations(range(1, n + 1)):
    ans += p < list(a) < q
print(ans)

复杂度分析

时间复杂度： $O(N\cdot N!)$ （枚举 $N!$ 个排列，每次比较 $O(N)$ ）
空间复杂度： $O(N)$

D - Pre-Palindrome

题目链接：https://atcoder.jp/contests/abc468/tasks/abc468_d

题目大意

定义"好串"为：至多重写（更改）一个字符就能变成回文串的字符串。例如 a、iwai、abcdcza 是好串，abcd、atcoder 不是好串（回文串本身也是好串）。给定字符串 $S$ ，求 $S$ 的所有非空子串中有多少是好串。位置不同的子串即使内容相同也分开计数。约束： $|S|\le 10^4$ 。

思路

关键观察：好串的刻画

先想清楚什么样的字符串是好串。注意这里的"回文"是位置上的对称（ $S_i=S_{|S|+1-i}$ ），而不是简单的字母奇偶频次条件。围绕一个中心，字符串的字符两两组成对称对（奇数长度时中间还有一个单独字符），而这些对称对是互不相交的位置对。

改写一个字符，只会改变这一个位置上的字符，因此最多只能"修复"一个错配的对称对；
反之，若整串错配的对称对不超过 1 对，则改写该对中的任意一个字符即可让全部对称对匹配，得到回文串。

因此结论是：一个子串是好串 $\iff$ 以它为中心展开时，对称位置不相等的"错配对"数量至多为 1。（注意：不要用"出现奇数次的不同字符数 $\le 3$ "这类频次判据——因为回文要求的是位置对称，例如 abdcb 有 3 个奇数次字符，但它有两个错配对称对，改一个字符无法成为回文。）

计数算法：中心扩展

既然判据与中心有关，就可以枚举每个中心并向外扩展：

奇数长度子串：中心为某个字符位置 $i$ 。令 $k=1,2,\ldots$ 逐步向外扩展，统计满足 $S_{i-k}\ne S_{i+k}$ 的对数 cnt。当 cnt 第一次达到 2 时，当前及更长的子串都至少有两个错配对，不再是好串，停止；否则每一个 $k$ （含 $k=0$ 的单个字符）都对应一个好串。
偶数长度子串：中心为两个相邻位置 $i$ 与 $i+1$ 之间的空隙。对称对为 $(S_{i-k}, S_{i+1+k})$ ，扩展方法与上面相同。

每个子串都有唯一的中心（奇数长度看中间字符，偶数长度看中间空隙），因此中心扩展能无重复、无遗漏地枚举所有子串。

正确性与易错点

当出现第二个错配对时，要先判断、再决定是否计数：出现第二个错配对的那个子串本身不是好串，不能计入答案（代码中 break 放在 ans++ 之前）；
单个字符子串（0 个错配对）一定是好串，不要漏掉；
回文子串（0 个错配对）也是好串。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin >> s;
    int n = (int)s.size();
    long long ans = 0;
    for (int t = 0; t < 2; t++) {          // t=0: 奇数长度, t=1: 偶数长度
        for (int st = 0; st < n; st++) {
            int l = st - t, r = st;        // 中心空隙（偶数）或中心字符（奇数）
            int cnt = 0;
            while (l >= 0 && r < n) {
                if (s[l] != s[r]) {
                    cnt++;
                    if (cnt == 2) break;   // 第 2 个错配对出现，本串及更长的串都不是好串
                }
                l--;
                r++;
                ans++;
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

s = input()
n = len(s)
ans = 0
for k in range(2):
    for st in range(n):
        l, r = st - k, st
        cnt = 0
        while 0 <= l and r < n:
            if s[l] != s[r]:
                cnt += 1
                if cnt == 2:
                    break
            l -= 1
            r += 1
            ans += 1
print(ans)

复杂度分析

时间复杂度： $O(N^2)$ （每个中心最多向外扩展 $O(N)$ 次；第二个错配对出现后提前终止）
空间复杂度： $O(1)$ （不计输入）

E - Sum of Average

题目链接：https://atcoder.jp/contests/abc468/tasks/abc468_e

题目大意

给定正整数 $N$ 和长度为 $N$ 的整数序列 $A$ ，记 $f(l,r)=\dfrac{A_l+A_{l+1}+\cdots+A_r}{r-l+1}$ 为子区间 $[l,r]$ 的算术平均值。求

\sum_{1\le l\le r\le N} f(l,r) \pmod{998244353}

约束： $N\le 5\times 10^5$ ， $0\le A_i < 998244353$ 。由于模数是素数且所有分母都 $\le N < MOD$ ，每个分数 $\frac{P}{Q}$ （ $Q\not\equiv 0$ ）都有唯一的模意义下表示 $R=P\cdot Q^{-1}\bmod MOD$ 。

思路

解法一：前缀和 + 调和数

设前缀和 $B_n=\sum_{k=1}^{n}A_k$ （ $B_0=0$ ），则 $f(l,r)=\dfrac{B_r-B_{l-1}}{r-l+1}$ 。原式可做如下变换（交换求和次序）：

\begin{aligned} \sum_{1\le l\le r\le N} f(l,r) &=\sum_{1\le l\le r\le N}\frac{B_r-B_{l-1}}{r-l+1}\\ &=\sum_{r=1}^{N}\sum_{l=1}^{r}\frac{B_r}{r-l+1}-\sum_{l=1}^{N}\sum_{r=l}^{N}\frac{B_{l-1}}{r-l+1}\\ &=\sum_{r=1}^{N}B_r H_r-\sum_{l=1}^{N}B_{l-1}H_{N-l+1}\\ &=\sum_{i=0}^{N}B_i\left(H_i-H_{N-i}\right), \end{aligned}

其中 $H_n=\sum_{k=1}^{n}\frac{1}{k}$ （ $H_0=0$ ）是调和数。最后一步把两个求和统一到 $i$ 上：第一个和贡献 $B_iH_i$ （ $i=1..N$ ），第二个和令 $i=l-1$ 贡献 $-B_iH_{N-i}$ （ $i=0..N-1$ ），合并即得。

于是只需 $O(N)$ 预处理 $B_i$ 与 $H_i$ ，再 $O(N)$ 求和即可。模意义下 $\frac{1}{k}$ 用 $k$ 的逆元 $k^{MOD-2}\bmod MOD$ （费马小定理）计算。

解法二：按 $A_i$ 统计贡献

也可以反过来，把每个 $A_i$ 对答案的贡献单独拆出来：

\begin{aligned} \sum_{1\le l\le r\le N} f(l,r) &=\sum_{1\le l\le r\le N}\sum_{i=l}^{r}\frac{A_i}{r-l+1} =\sum_{i=1}^{N}A_i\sum_{l=1}^{i}\sum_{r=i}^{N}\frac{1}{r-l+1}\\ &=\sum_{i=1}^{N}A_i\sum_{l=1}^{i}\left(H_{N-l+1}-H_{i-l}\right) =\sum_{i=1}^{N}A_i\sum_{j=0}^{i-1}\left(H_{N-j}-H_j\right). \end{aligned}

记 $S_i=\sum_{j=0}^{i-1}(H_{N-j}-H_j)$ ，有递推 $S_{i+1}=S_i+(H_{N-i}-H_i)$ ，同样可 $O(N)$ 完成。

为什么正确

上述变换只是有限和的求和次序交换，每一项 $f(l,r)$ 恰被计算一次；交换次序不改变结果。模运算下，所有分母不超过 $N<MOD$ ，逆元均存在，运算封闭，故结果唯一。

参考代码

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 998244353;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> inv(n + 1), h(n + 1), b(n + 1);
    inv[1] = 1;
    for (int i = 2; i <= n; i++)                 // 线性求逆元
        inv[i] = MOD - (MOD / i) * inv[MOD % i] % MOD;
    for (int i = 1; i <= n; i++)
        h[i] = (h[i - 1] + inv[i]) % MOD;        // 调和数 H_i
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        b[i] = (b[i - 1] + x) % MOD;             // 前缀和 B_i
    }
    long long ans = 0;
    for (int i = 0; i <= n; i++) {
        ans = (ans + b[i] * (h[i] - h[n - i])) % MOD;
    }
    ans = (ans % MOD + MOD) % MOD;               // 处理负数
    cout << ans << '\n';
    return 0;
}

n = int(input())
a = list(map(int, input().split()))
MOD = 998244353
b = [0] * (n + 1)
for i in range(n):
    b[i + 1] = (b[i] + a[i]) % MOD
h = [0] * (n + 1)
for i in range(1, n + 1):
    h[i] = (h[i - 1] + pow(i, MOD - 2, MOD)) % MOD
ans = 0
for i in range(n + 1):
    ans = (ans + b[i] * (h[i] - h[n - i])) % MOD
print(ans)

复杂度分析

时间复杂度： $O(N)$
空间复杂度： $O(N)$

F - Chmax

题目链接：https://atcoder.jp/contests/abc468/tasks/abc468_f

题目大意

有变量 $x,y,c$ ，初始均为 $0$ 。对 $k=1,2,\ldots,N$ ，依次对 $P_k$ 执行两种操作之一：

操作 1：若 $x < P_k$ 则 $c$ 加 1；然后 $x\gets \max(x,P_k)$ ；
操作 2：若 $y < P_k$ 则 $c$ 加 1；然后 $y\gets \max(y,P_k)$ 。

$P$ 是 $(1,2,\ldots,N)$ 的一个排列。求 $c$ 最终能达到的最大值。约束： $N\le 5\times 10^5$ 。

思路

状态约简

直接设 $dp[i][p][q]$ 表示处理完前 $i$ 个元素后 $x=p,y=q$ 时的最大 $c$ ，状态数是 $O(N^3)$ ，不可行。关键观察是：

无论怎么操作，始终有 $\max(x,y)=\max(P_1,P_2,\ldots,P_k)$ 。

因为每一步都把某个变量更新为 $\max(\text{旧值},P_k)$ ，两者中的最大值总是变成当前前缀的最大值。因此"较大值"完全由前缀决定，状态中只需要记录 $\min(x,y)$ 。设 $d[i][p]$ 表示处理完前 $i$ 个元素、 $\min(x,y)=p$ 时 $c$ 的最大值（不可达则为 $-\infty$ ）。

转移

设 $P_i=v$ ，处理前的前缀最大值为 $m$ 。

情形 1： $v < m$ （非新纪录）。两个变量值分别为 $j=\min$ 与 $m=\max$ ：

把 $v$ 赋给较小值的变量（ $j<v$ ）：因为 $j<v$ ， $c$ 加 1，新的 $\min$ 变为 $v$ ；
把 $v$ 赋给较大值的变量（ $m>v$ ）： $c$ 不变， $\min$ 保持 $j$ ；
若 $j\ge v$ ：无论赋给谁， $v$ 都不会生效， $c$ 不变， $\min$ 不变。

因此 $$d[i][v]=\max\left(d[i-1][v],\ \max_{1\le j<v}d[i-1][j]+1\right),\qquad d[i][p]=d[i-1][p]\ (p\ne v).$$

情形 2： $v > m$ （新纪录）。无论赋给哪个变量， $c$ 都加 1。若赋给较大的变量， $\min$ 不变；若赋给较小的变量， $\min$ 变成 $v$ （变大）。 $\min$ 更小总是更优的（可以归纳证明： $\min$ 更小的状态对任意未来序列都能得到不差的结果），所以总是把 $v$ 赋给较大值的变量，即

d[i][p]=d[i-1][p]+1\quad(\forall p).

实现技巧

情形 2 要对所有 $p$ 整体加 1，若用数据结构维护则需要懒标记。注意到记录型元素对 $c$ 的贡献是确定的 +1，我们把它单独累计到 rec 中，而用线段树/树状数组维护"减去已累计记录数"后的数组 $d'$ 。记录元素到来时不修改 $d'$ ；非记录元素 $v$ 到来时执行

d'[v]\gets\max\left(d'[v],\ \max_{j<v}d'[j]+1\right),

这恰好是"按数值的 LIS 转移"。用支持前缀最大值查询 + 单点取 max 更新的树状数组即可 $O(N\log N)$ 完成。最终答案 $=\#\text{记录} + \max_p d'[p]$ 。

LIS 等价观察

由转移的形式可以看出：若把 $P$ 中所有"新纪录"元素（ $P_i>\max(P_1,\ldots,P_{i-1})$ ）剔除，剩下的序列记为 $Q$ ，则 $d'$ 的转移正是对 $Q$ 求最长上升子序列（LIS）的经典 DP，故

\text{答案} = \#\text{纪录元素} + \text{LIS}(Q).

用二分 + 贪心的 LIS 算法也可得到 $O(N\log N)$ 的解，这是官方给出的另一种简洁做法。

参考代码

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

struct FenwickMax {          // 前缀最大值，下标从 1 开始
    int n;
    vector<int> bit;
    FenwickMax(int n_) : n(n_), bit(n_ + 2, -1) {}
    void update(int i, int v) {
        for (; i <= n; i += i & -i) bit[i] = max(bit[i], v);
    }
    int query(int i) {       // [1, i] 的最大值
        int r = -1;
        for (; i > 0; i -= i & -i) r = max(r, bit[i]);
        return r;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    FenwickMax fw(n + 1);            // 下标 = 值 + 1，覆盖值 0..n
    vector<int> dval(n + 1, -1);     // d'[p] 的点值
    dval[0] = 0;
    fw.update(1, 0);                 // 值 0 对应下标 1
    int rec = 0, ma = 0;
    for (int i = 0; i < n; i++) {
        int v;
        cin >> v;
        if (ma < v) {                // 新纪录：贡献 +1，单独计数
            ma = v;
            rec++;
        } else {                     // 非纪录：d'[v] = max(d'[v], max_{j<v} d'[j] + 1)
            int best = fw.query(v) + 1;   // 值 0..v-1 对应下标 1..v
            int nv = max(dval[v], best);
            if (nv > dval[v]) {
                dval[v] = nv;
                fw.update(v + 1, nv);
            }
        }
    }
    cout << rec + fw.query(n + 1) << '\n';
    return 0;
}

官方给出的 LIS 做法（Python）：

import bisect

def lis(seq):
    if len(seq) == 0:
        return 0
    LIS = [seq[0]]
    for x in seq:
        if x > LIS[-1]:
            LIS.append(x)
        else:
            LIS[bisect.bisect_left(LIS, x)] = x
    return len(LIS)

n = int(input())
p = list(map(int, input().split()))
q = []
ans = 0
mx = -1
for v in p:
    if mx < v:
        mx = v
        ans += 1          # 纪录元素
    else:
        q.append(v)       # 非纪录元素
print(ans + lis(q))

复杂度分析

时间复杂度： $O(N\log N)$ （树状数组版本与 LIS 版本均为 $O(N\log N)$ ）
空间复杂度： $O(N)$

G - Restricted Permutation

题目链接：https://atcoder.jp/contests/abc468/tasks/abc468_g

题目大意

给定正整数 $N$ 和长度为 $N$ 的字符串 $S$ （由 o 和 x 组成）。求满足下述条件的排列 $P=(P_1,\ldots,P_N)$ 的数量（模 $998244353$ ）：对每个 $k=1,2,\ldots,N$ ， $S_k=$ o 当且仅当 $P$ 中含有 $(1,2,\ldots,k)$ 的一个排列作为连续子序列。约束： $N\le 2000$ 。

思路

问题转化：连续子序列 $\iff$ 位置集合连续

记 $\mathrm{pos}_i$ 为数值 $i$ 在 $P$ 中的位置。 $P$ 中存在一个长度为 $k$ 的连续子段恰好是 $(1,\ldots,k)$ 的某个排列，当且仅当这 $k$ 个位置恰好承载了数值 $1..k$ ，即

\{\mathrm{pos}_1,\mathrm{pos}_2,\ldots,\mathrm{pos}_k\}\ \text{构成一段连续的位置区间}.

因此原条件等价于： $S_k=$ o $\iff$ $\{\mathrm{pos}_1,\ldots,\mathrm{pos}_k\}$ 连续。

首先，任何排列都含有长度 1 的 $(1)$ 与长度 $N$ 的 $(1,2,\ldots,N)$ 作为连续子序列，所以若 $S_1=$ x 或 $S_N=$ x，答案为 $0$ 。

基础块：模式 `oxx...xxo`

设 $d_n$ 为当 $S$ 是"两端为 o、中间全为 x"的长度 $n$ 的串（记作 oxx...xxo）时，满足条件的排列数。 $d_n$ 就是满足" $\{\mathrm{pos}_1,\ldots,\mathrm{pos}_k\}$ 仅在 $k=1$ 与 $k=n$ 时连续"的 $(1,\ldots,n)$ 的排列数。

如何计算 $d_n$ ？对 $(1,\ldots,n)$ 的任意排列，考虑最小的 $k\ge 2$ 使得 $\{\mathrm{pos}_1,\ldots,\mathrm{pos}_k\}$ 连续。最小值为 $k$ 的排列可以这样构成：

内部：数值 $1..k$ 的相对顺序必须使得 $\{\mathrm{pos}_1,\ldots,\mathrm{pos}_j\}$ 对 $2\le j\le k-1$ 都不连续、对 $j=k$ 连续——这正好是 $d_k$ 种；
外部：数值 $k+1,\ldots,n$ 全部落在该连续块之外。块有 $n-k+1$ 个可放置的起始位置，其余 $n-k$ 个元素任意排列，共 $(n-k+1)!$ 种。

每个排列被唯一确定地计数一次，故

n!=\sum_{k=2}^{n} d_k\,(n-k+1)!

移项即得 $d_n=n!-\sum_{k=2}^{n-1} d_k\,(n-k+1)!$ ，且 $d_1=1$ 。按 $n$ 从小到大 $O(N^2)$ 递推即可。验证： $d_2=2$ ， $d_3=6-d_2\cdot 2!=2$ ， $d_4=24-d_2\cdot 3!-d_3\cdot 2!=8$ 。

一般串：连续块之间的独立性

设 $S$ 中所有 o 的位置为 $1=A_1<A_2<\cdots<A_M=N$ 。答案可以分解为连续相邻 o 之间的块的乘积：

\text{答案}=\prod_{i=1}^{M-1} d_{A_{i+1}-A_i+1}.

为什么可以分块相乘。 在最终排列 $P$ 中，数值 $1..A_i$ 占据一个连续区间 $I_{A_i}$ ，且区间嵌套 $I_{A_1}\subseteq I_{A_2}\subseteq\cdots\subseteq I_{A_M}=[1,N]$ 。第一个块： $1..A_2$ 在区间 $I_{A_2}$ 内的相对顺序必须满足"仅 $k=1$ 和 $k=A_2$ 时连续"，恰为 $d_{A_2}$ 种。对于后续每个块（数值 $A_i+1..A_{i+1}$ ），它们全部位于 $I_{A_i}$ 之外（否则会破坏 $I_{A_i}$ 的连续性），且 $I_{A_{i+1}}\setminus I_{A_i}$ 是 $I_{A_i}$ 左右两侧的延伸。把 $I_{A_i}$ 整体"收缩"成一个点后，关于" $\{\text{前 }k\text{ 个数值}\}$ 何时连续"的条件完全对应到模式 oxx...xxo（长度 $A_{i+1}-A_i+1$ ，其中收缩出的点扮演最小元素 $1$ ），因此该块内部的相对安排恰有 $d_{A_{i+1}-A_i+1}$ 种，且不同块的安排互不影响（它们占据互不相交的位置集合）。各块独立，故总数为乘积。

算法与复杂度

递推 $d_2,\ldots,d_N$ 需 $O(N^2)$ ， $N\le 2000$ 时约 $4\times 10^6$ 次模乘，完全可行。若追求更优，官方题解指出可以用形式幂级数（FPS）技巧将递推优化到 $O(N\log N)$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    string s;
    cin >> n >> s;
    const long long MOD = 998244353;
    if (s[0] == 'x' || s[n - 1] == 'x') {   // 首尾必须为 o
        cout << 0 << '\n';
        return 0;
    }
    vector<long long> fac(n + 1, 1);
    for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % MOD;
    // d[i]: 模式 "oxx...xxo"（长度 i）的合法排列数
    vector<long long> d(n + 1, 0);
    d[1] = 1;
    for (int i = 2; i <= n; i++) {
        long long val = fac[i];
        for (int k = 2; k < i; k++) {
            val = (val - d[k] * fac[i - k + 1]) % MOD;   // n! = Σ d_k (n-k+1)!
        }
        d[i] = (val % MOD + MOD) % MOD;
    }
    long long ans = 1;
    int prev = -1;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'o') {
            if (prev != -1) ans = ans * d[i - prev + 1] % MOD;  // 块长 = A_{i+1}-A_i+1
            prev = i;
        }
    }
    cout << ans << '\n';
    return 0;
}

n = int(input())
s = input()
MOD = 998244353
if s[0] == 'x' or s[-1] == 'x':
    print(0)
    exit()
fac = [1] * (n + 1)
for i in range(1, n + 1):
    fac[i] = fac[i - 1] * i % MOD
d = [0] * (n + 1)
d[1] = 1
for i in range(2, n + 1):
    d[i] = fac[i]
    for k in range(2, i):
        d[i] -= d[k] * fac[i - k + 1]
        d[i] %= MOD
ans = 1
for x in s.split('o')[1:-1]:        # 相邻 o 之间的 x 段
    ans *= d[len(x) + 2]
    ans %= MOD
print(ans)

复杂度分析

时间复杂度： $O(N^2)$
空间复杂度： $O(N)$