Znzryb's Blog

Codeforces Round 1083 (Div. 2)——CF-2205-E. Simons and Dividing the Rhythm（分析分段 rev 操作的方法即 \text{rev}(XY) = \text{rev}(Y)\text{rev}(X)）

Posted on 2026-03-02 Edited on 2026-03-03

题目大意

题目描述

给定一个长度为 $n$ 的目标数组 $T$ 。

现有一个与 $T$ 等长的初始数组 $S$ ，对 $S$ 进行恰好一次如下操作：
选择一个整数 $k$ ，并将数组 $S$ 划分为 $k$ 个连续且不重叠的子段。假设这 $k$ 个子段的下标区间依次为 $[l_1, r_1], [l_2, r_2], \dots, [l_k, r_k]$ ，满足 $l_1=1$ ， $r_k=n$ ，且对于所有的 $1 \le i \le k-1$ ，都有 $r_i + 1 = l_{i+1}$ 。
然后，对这 $k$ 个子段分别独立地进行翻转操作。

即，选择的区间形如：

请求出有多少种不同的初始数组 $S$ ，可以通过上述操作变为目标数组 $T$ 。由于答案可能很大，请输出其对 $998244353$ 取模后的结果。

输入格式

第一行包含一个整数 $t$ （ $1 \le t \le 8000$ ），表示测试用例的数量。
每组测试用例的第一行包含一个整数 $n$ （ $1 \le n \le 8000$ ），表示数组的长度。
第二行包含 $n$ 个整数 $T_1, T_2, \dots, T_n$ （ $1 \le T_i \le 8000$ ），表示目标数组 $T$ 的元素。
保证所有测试用例中 $n$ 的总和不超过 $8000$ 。

输出格式

对于每组测试用例，输出一个整数，表示满足条件的数组 $S$ 的数量对 $998244353$ 取模后的结果。

样例输入

5
4
1 1 2 1
4
1 2 3 1
6
1 3 2 3 3 2
10
2 3 1 4 3 1 4 3 1 2
1
8000

样例输出

样例解释

在第一组测试用例中， $T = [1, 1, 2, 1]$ ，以下 $4$ 种数组 $S$ 可以被转换为 $T$ ：

对于 $S = [2, 1, 1, 1]$ ，可以选择区间 $[1, 3]$ 和 $[4, 4]$ 进行翻转。翻转后数组变为 $[1, 1, 2, 1]$ ，等于 $T$ 。
对于 $S = [1, 2, 1, 1]$ ，可以选择区间 $[1, 4]$ 进行翻转。
对于 $S = [1, 1, 2, 1]$ ，可以选择区间 $[1, 2]$ 、 $[3, 3]$ 和 $[4, 4]$ 进行翻转。
对于 $S = [1, 1, 1, 2]$ ，可以选择区间 $[1, 2]$ 和 $[3, 4]$ 进行翻转。

在第二组测试用例中， $T = [1, 2, 3, 1]$ ，以下 $7$ 种数组 $S$ 可以被转换为 $T$ ：

对于 $S = [1, 1, 3, 2]$ ，可以选择区间 $[1, 1]$ 和 $[2, 4]$ 进行翻转。
对于 $S = [1, 2, 1, 3]$ ，可以选择区间 $[1, 1]$ 、 $[2, 2]$ 和 $[3, 4]$ 进行翻转。
对于 $S = [1, 2, 3, 1]$ ，可以选择区间 $[1, 1]$ 、 $[2, 2]$ 、 $[3, 3]$ 和 $[4, 4]$ 进行翻转。
对于 $S = [1, 3, 2, 1]$ ，可以选择区间 $[1, 4]$ 进行翻转。
对于 $S = [2, 1, 1, 3]$ ，可以选择区间 $[1, 2]$ 和 $[3, 4]$ 进行翻转。
对于 $S = [2, 1, 3, 1]$ ，可以选择区间 $[1, 2]$ 、 $[3, 3]$ 和 $[4, 4]$ 进行翻转。
对于 $S = [3, 2, 1, 1]$ ，可以选择区间 $[1, 3]$ 和 $[4, 4]$ 进行翻转。

思路讲解

分析 rev 操作的一个重要公式是：

$\text{rev}(XY) = \text{rev}(Y)\text{rev}(X)$

可以继续拓展：

所以，我们要求转移时前缀相同，只采用这一后缀，即可得到独特的计数。

具体来讲，我们对这一后缀的要求是（在前缀相同的情况下）这一后缀无论如何划分，都达不到整体的效果。

1	rev(S) != rev(任意对S的划分方法)

比如说 [1, 2, 3, 4] 任何其他划分方式都达不到 rev([1, 2, 3, 4]) 的效果。

不过上面，opus4.6 给出的解释实际上不是很令人满意，因为带有非常明显的知道答案，凑出证明的痕迹。我们采用一种更加好的方法？（可能没有那么严谨，但是实际上是严谨的）

P4391 [BalticOI 2009] Radio Transmission 无线传输

我们不难发现，可以这种所谓的查找目标 $C=C'$ ，其实就是查找周期，其实和查找周期的哈希实现一模一样（详见上面一道题目）。

相信看了我的这个解释，应该都能看出来这个东西。

其实，形如 $rev(S)=rev(ABA)$ ，其实是唯一一种形式，可以保证分段反转等于整体反转。

不过快速检查一个字符串是否有真前后缀相同，显然是使用 kmp（前缀数组，前缀数组就是这么定义的，能不好吗？）还是比较好的，使用字符串哈希时间复杂度不是很优秀。

P3375 【模板】KMP（前缀函数）

好，现在问题就来到了，我们怎么样求 $s[l;r]$ 是否有这个真前后缀匹配情况？

哈哈，其实解决这个问题的方法也很简单，那么就是跑 n 遍 kmp 就可以了，这道题目不是 $O(n^2)$ 的嘛。绷不住了。

vector<ll> kmp(ll N,const vector<ll> &A){	// 返回总前缀数组pi
    vector<ll> pi(N+2);
    for(int i=2;i<=N;++i){
        ll len=pi[i-1];
        // if(S[i]==S[len+1]){
        // pi[i]=len+1;
        // }
        while(true){
            if(A[i]==A[len+1]){
                pi[i]=len+1;
                break;
            }
            if(len==0) break;
            len=pi[len];
        }
    }
    return pi;
}

最后的这个 dp 代码：

for (int l=1;l<=N;++l) {
    vector<ll> pi=kmp(N-l+1,vector<ll>(A.begin()+l-1,A.end()));
    ll offset=l-1;
    for (int r=l;r<=N;++r) {
        if (pi[r-offset]>0) {
            continue;
        }
        dp[r]+=dp[l-1];
        dp[r]%=mod;
    }
}

AC代码

AC
https://codeforces.com/contest/2205/submission/365177121

这个代码跑的好快啊，竟然

源代码

/**
 * Problem: E. Simons and Dividing the Rhythm
 * Contest: Codeforces Round 1083 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2205/problem/E
 * Created: 2026-03-02 12:26:01
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */

vector<ll> kmp(ll N,const vector<ll> &A){	// 返回总前缀数组pi
    vector<ll> pi(N+2);
    for(int i=2;i<=N;++i){
        ll len=pi[i-1];
        // if(S[i]==S[len+1]){
        // pi[i]=len+1;
        // }
        while(true){
            if(A[i]==A[len+1]){
                pi[i]=len+1;
                break;
            }
            if(len==0) break;
            len=pi[len];
        }
    }
    return pi;
}
void Solve() {
    ll N;
    cin >> N;
    vector<ll> A(N+2);
// #ifdef LOCAL
//     do {
//         Hash hs(4,{0,1,10,1,10});
//         assert(hs.getlr(1,2)==hs.getlr(3,4));
//     }while (false);
// #endif
    for (int i=1;i<=N;++i) {
        cin>>A[i];
    }

    vector<ll> dp(N+2);
    dp[0]=1;
    // auto check_suf_pre=[&](ll l,ll r) -> bool {
    //     if () {
    //
    //     }
    // };
    for (int l=1;l<=N;++l) {
        vector<ll> pi=kmp(N-l+1,vector<ll>(A.begin()+l-1,A.end()));
        ll offset=l-1;
        for (int r=l;r<=N;++r) {
            if (pi[r-offset]>0) {
                continue;
            }
            dp[r]+=dp[l-1];
            dp[r]%=mod;
        }
    }
    cout<<dp[N]<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2205/submission/365177121

*/

心路历程（WA，TLE，MLE……）

要好好想清楚这个 dp 是从哪里转移过来的，是从 l-1 转移过来的。

for (int l=1;l<=N;++l) {
    vector<ll> pi=kmp(N-l+1,vector<ll>(A.begin()+l-1,A.end()));
    ll offset=l-1;
    for (int r=l;r<=N;++r) {
        if (pi[r-offset]>0) {
            continue;
        }
        dp[r]+=dp[l-1];
        dp[r]%=mod;
    }
}

下面是废掉的 AI 提示

OPUS 4.6

题意转化
题目要求：给定目标数组 $T$ ，有多少个不同的初始数组 $S$ ，使得存在某种将 $S$ 切成若干连续段后分别翻转能得到 $T$ 。
由于"分段翻转"是自逆操作（对同一分段再做一次翻转就还原）， $S$ 能变成 $T$ 当且仅当 $T$ 用同样的分段翻转能变成 $S$ 。因此问题等价于：

把 $T$ 切成若干连续段并分别翻转，能得到多少种不同的数组？
核心观察：何时两种切法产生同一结果
设切法 1 的最后一段是 $[j_1+1, i]$ ，切法 2 的最后一段是 $[j_2+1, i]$ （ $j_1 < j_2$ ）。经过推导可知，它们在位置 $j_2+1$ 到 $i$ 上的值相同当且仅当：

T[q] = T[q + d], \quad j_1+1 \le q \le i - d, \quad d = j_2 - j_1

即子串 $T[j_1+1..i]$ 具有周期 $d$ 。
关键引理：非本原段可以缩短
若 $T[j+1..i]$ 具有周期 $d < i - j$ （即该子串不是"本原的"），则所有以 $[j+1, i]$ 为最后一段能产生的结果，都能通过以 $[j+d+1, i]$ 为最后一段来实现。
证明思路：将最后一段 $[j+1, i]$ 的前 $d$ 个字符"吸收"到前缀中——由于周期性，这前 $d$ 个翻转后的值恰好等于对 $T[j+1..j+d]$ 的某种合法分段翻转结果（具体地，用切点 $j+r$ 把它分成两段，其中 $r = (i-j) \bmod d$ ）。
推论：本原段之间不产生重复
若两个最后一段 $[j_1+1, i]$ 和 $[j_2+1, i]$ 都是本原的（最小周期等于自身长度），则 $j_1 \ne j_2$ 时它们产生的结果集合完全不交。因为若有交集，较长的那个子串就会有周期 $|j_2 - j_1|$ ，与本原性矛盾。
DP 公式
设 $dp[i]$ 为 $T[1..i]$ 能产生的不同结果数。由以上分析：

dp[i] = \sum_{\substack{j=0 \\ T[j+1..i] \text{ 是本原的}}}^{i-1} dp[j]

其中 $dp[0] = 1$ 。每一项互不重叠，无需容斥。
如何判断本原性
子串 $T[j+1..i]$ 是本原的当且仅当它的最小周期等于其长度。利用 KMP 的失配函数（failure function）：长度为 $L$ 的字符串的最小周期为 $L - \text{fail}[L]$ ，因此本原等价于 $\text{fail}[L] = 0$ 。
对于固定的终点 $i$ ，我们考虑反串 $R_i = T[i], T[i-1], \ldots, T[1]$ ，则子串 $T[j+1..i]$ 对应 $R_i$ 的前缀 $R_i[1..i-j]$ 。对 $R_i$ 跑一次 KMP 即可得到所有前缀长度 $L$ 处的 $\text{fail}[L]$ ，从而判断哪些 $j$ 对应本原段。
复杂度
对每个 $i$ ，KMP 和求和各 $O(i)$ ，总复杂度 $O(n^2)$ 。 $n \le 8000$ ，完全可行。

OPUS4.6 对我提出疑问的解答

这是个好问题，我来讲清楚。

你的疑惑

证明"非本原段可被更短段覆盖"时，我们说：

切法 1（最后一段 $[j_1+1, i]$ ）和切法 2（最后一段 $[j_2+1, i]$ ）给出同一个结果 $R$ 。
你的疑问是：“这要求两个切法的前缀部分产生相同的值，但 dp 本身在数不同的结果，这不矛盾吗？”

其实不矛盾，因为两个前缀是不同长度的对象

关键： $R'_1$ 和 $R'_2$ 不是同一个东西。

$R'*1 \in \mathcal{R}*{j_1}$ ：是 $T[1..j_1]$ 的某个结果（长度 $j_1$ ）
$R'*2 \in \mathcal{R}*{j_2}$ ：是 $T[1..j_2]$ 的某个结果（长度 $j_2 > j_1$ ）
$R'_2$ 是从 $R'_1$ 扩展出来的：保留 $R'_1$ 的前 $j_1$ 个位置，再附加 $T[j_1+1..j_2]$ 的某种分段翻转结果。

用样例 1 具体看

$T = [1, 1, 2, 1]$ ， $i = 4$ ， $j_1 = 0$ ， $j_2 = 3$ ， $d = 3$ 。
切法 1：最后一段 $[1, 4]$ ，前缀为空。

R = \text{rev}(T[1..4]) = [1, 2, 1, 1]

切法 2：最后一段 $[4, 4]$ ，前缀是 $T[1..3]$ 的某个结果。
要得到同一个 $R = [1, 2, 1, 1]$ ：

位置 4 $= T[4] = 1$ ✓（周期条件保证 $T[1] = T[4]$ ）
前缀 $R'_2[1..3]$ 必须 $= [1, 2, 1]$
问题： $[1, 2, 1]$ 是 $T[1..3] = [1, 1, 2]$ 的一个合法结果吗？
是的！用分段 $\{[1,1], [2,3]\}$ ： $[1] \circ \text{rev}([1,2]) = [1, 2, 1]$ 。✓
所以 $R'_2 = [1, 2, 1]$ 确实存在于 $\mathcal{R}_3$ 中。不需要"凭空创造"，它本来就是 $T[1..3]$ 的 $dp_3 = 3$ 个结果之一。

逻辑链条

整个推理没有循环：

给定一个具体的结果 $R$ ，它来自非本原的最后一段 $[j_1+1, i]$
我们构造一个 $R'_2$ ：把 $R'_1$ 后面接上 $T[j_1+1..j_2]$ 的一种特定分段翻转
由于分段翻转是合法操作， $R'*2$ 一定是* $T[1..j_2]$ 的一个可达结果*（它在 $\mathcal{R}*{j_2}$ 中）
由于周期条件， $R'_2 \circ \text{rev}(T[j_2+1..i]) = R$ （同一个结果）
所以 $R$ 已经被更短的最后一段 $[j_2+1, i]$ 覆盖了
不需要假设"前缀相同"—— $R'_2$ 是从 $R'_1$ 推导构造出来的，不是假设出来的。而且 $R'_1$ （长度 $j_1$ ）和 $R'_2$ （长度 $j_2$ ）是不同长度的前缀，不存在"不允许相同"的问题。

OPUS 4.6 模拟样例

好的，我用前三个样例来逐步模拟。

回顾算法核心

$dp_0 = 1$ （空前缀，一种结果）
对每个终点 $i$ ，构造反串 $R_i = T[i], T[i-1], \ldots, T[1]$ ，对 $R_i$ 求 KMP 失配函数
$R_i$ 的前缀长度 $L$ 对应子串 $T[i-L+1..i]$ （即以 $i$ 结尾、长度为 $L$ 的最后一段）
$\text{fail}[L] = 0$ 意味着该子串是本原的（最小周期 $= L$ ），对 $dp_i$ 有贡献
$\text{fail}[L] > 0$ 意味着存在更短周期，该段产生的结果被更短段"覆盖"，跳过

样例 1： $T = [1, 1, 2, 1]$ ，答案 $= 4$

$i = 1$ ： $R_1 = [1]$

$L$	$R_1[1..L]$	$\text{fail}$	本原？	对应子串
1	$[1]$	0	是	$T[1..1]=[1]$

dp_1 = dp_0 = 1

$i = 2$ ： $R_2 = [1, 1]$

$L$	$R_2[1..L]$	$\text{fail}$	本原？	对应子串
1	$[1]$	0	是	$T[2..2]=[1]$
2	$[1,1]$	1	否	$T[1..2]=[1,1]$ ，周期 1
$L=2$ 时 $[1,1]$ 有周期 1（两个字符相同），非本原，跳过。

dp_2 = dp_1 = 1

含义： $T[1..2]=[1,1]$ 无论怎么切（切或不切），翻转后都是 $[1,1]$ ，只有 1 种结果。
$i = 3$ ： $R_3 = [2, 1, 1]$

$L$	$R_3[1..L]$	$\text{fail}$	本原？	对应子串
1	$[2]$	0	是	$T[3..3]=[2]$
2	$[2,1]$	0	是	$T[2..3]=[1,2]$
3	$[2,1,1]$	0	是	$T[1..3]=[1,1,2]$
三段都是本原的！

dp_3 = dp_2 + dp_1 + dp_0 = 1 + 1 + 1 = 3

含义： $T[1..3]=[1,1,2]$ 的三种不同结果是：

最后一段 $[3,3]$ （ $L=1$ ）：前缀 $T[1..2]$ 有 $dp_2=1$ 种结果 $\to$ $[1,1,2]$
最后一段 $[2,3]$ （ $L=2$ ）：前缀 $T[1..1]$ 有 $dp_1=1$ 种结果 $\to$ $[1,2,1]$
最后一段 $[1,3]$ （ $L=3$ ）：前缀为空， $dp_0=1$ 种 $\to$ $[2,1,1]$
$i = 4$ ： $R_4 = [1, 2, 1, 1]$
| $L$ | $R_4[1..L]$ | $\text{fail}$ | 本原？ | 对应子串 | 说明 |
| — | — | — | — | — | — |
| 1 | $[1]$ | 0 | 是 | $T[4..4]=[1]$ | |
| 2 | $[1,2]$ | 0 | 是 | $T[3..4]=[2,1]$ | |
| 3 | $[1,2,1]$ | 1 | 否 | $T[2..4]=[1,2,1]$ | 周期 2（ $T[2]=T[4]=1$ ） |
| 4 | $[1,2,1,1]$ | 1 | 否 | $T[1..4]=[1,1,2,1]$ | 周期 3（ $T[1]=T[4]=1$ ） |
$L=3$ ： $[1,2,1]$ 的前缀 $[1]$ 等于后缀 $[1]$ ， $\text{fail}=1$ ，最小周期 $= 3-1 = 2 < 3$ ，非本原。这意味着用 $T[2..4]=[1,2,1]$ 做最后一段的所有结果，都能被更短的最后一段覆盖。
$L=4$ ： $[1,2,1,1]$ 的前缀 $[1]$ 等于后缀 $[1]$ ， $\text{fail}=1$ ，最小周期 $= 4-1 = 3 < 4$ ，非本原。同理跳过。

dp_4 = dp_3 + dp_2 = 3 + 1 = \boxed{4}

验证：4 种不同的 $S$ 分别是：

最后一段 $[4,4]$ （ $L=1$ ），前缀 $T[1..3]$ 有 3 种结果 $\to$ $S \in \{[1,1,2,1],\ [1,2,1,1],\ [2,1,1,1]\}$
最后一段 $[3,4]$ （ $L=2$ ），前缀 $T[1..2]$ 有 1 种结果 $\to$ $S = [1,1,1,2]$
共 4 种。

样例 2： $T = [1, 2, 3, 1]$ ，答案 $= 7$

$i = 1$ ： $R_1=[1]$ ，fail $=[0]$ 。 $dp_1 = 1$ 。
$i = 2$ ： $R_2=[2,1]$ ，fail $=[0, 0]$ 。两段都本原。

dp_2 = dp_1 + dp_0 = 1 + 1 = 2

（ $T[1..2]=[1,2]$ ：切或不切给出 $[1,2]$ 和 $[2,1]$ ，2 种结果）
$i = 3$ ： $R_3=[3,2,1]$ ，fail $=[0, 0, 0]$ 。三段都本原（所有字符互不相同）。

dp_3 = dp_2 + dp_1 + dp_0 = 2 + 1 + 1 = 4

$i = 4$ ： $R_4=[1, 3, 2, 1]$

$L$	$R_4[1..L]$	$\text{fail}$	本原？	对应子串
1	$[1]$	0	是	$T[4..4]=[1]$
2	$[1,3]$	0	是	$T[3..4]=[3,1]$
3	$[1,3,2]$	0	是	$T[2..4]=[2,3,1]$
4	$[1,3,2,1]$	1	否	$T[1..4]=[1,2,3,1]$ ，周期 3（ $T[1]=T[4]=1$ ）
只有 $L=4$ 被排除（整段 $T[1..4]$ 有周期 3）。

dp_4 = dp_3 + dp_2 + dp_1 = 4 + 2 + 1 = \boxed{7}

验证：7 种 $S$ 的来源：

最后一段 $[4,4]$ （ $L=1$ ）：前缀 $T[1..3]$ 有 4 种 $\to$ 4 个 $S$
最后一段 $[3,4]$ （ $L=2$ ）：前缀 $T[1..2]$ 有 2 种 $\to$ 2 个 $S$
最后一段 $[2,4]$ （ $L=3$ ）：前缀 $T[1..1]$ 有 1 种 $\to$ 1 个 $S$
$4 + 2 + 1 = 7$ ，且这三组之间无重复（因为每组的最后一段是本原的，不同本原段不产生交叉）。

样例 3： $T = [1, 3, 2, 3, 3, 2]$ ，答案 $= 22$

更快速地走一遍：

$i$	$R_i$	fail 数组	本原的 $L$ 值	DP 转移	$dp_i$
0	—	—	—	—	1
1	$[1]$	$[0]$	1	$dp_0$	1
2	$[3,1]$	$[0,0]$	1, 2	$dp_1 + dp_0$	2
3	$[2,3,1]$	$[0,0,0]$	1, 2, 3	$dp_2+dp_1+dp_0$	4
4	$[3,2,3,1]$	$[0,0,\mathbf{1},0]$	1, 2, 4	$dp_3+dp_2+dp_0$	7
5	$[3,3,2,3,1]$	$[0,\mathbf{1},0,\mathbf{1},0]$	1, 3, 5	$dp_4+dp_2+dp_0$	10
6	$[2,3,3,2,3,1]$	$[0,0,0,\mathbf{1},\mathbf{2},0]$	1, 2, 3, 6	$dp_5+dp_4+dp_3+dp_0$	22
最后一行详细解释：
$R_6 = [2, 3, 3, 2, 3, 1]$ ，KMP 失配函数：

$L=4$ ： $R_6[1..4]=[2,3,3,2]$ ，前缀 $[2]$ = 后缀 $[2]$ ， $\text{fail}=1$ ，周期 $3$ ——对应 $T[3..6]=[2,3,3,2]$ 有周期 3（ $T[3]=T[6]=2$ ），非本原，跳过
$L=5$ ： $R_6[1..5]=[2,3,3,2,3]$ ，前缀 $[2,3]$ = 后缀 $[2,3]$ ， $\text{fail}=2$ ，周期 $3$ ——对应 $T[2..6]=[3,2,3,3,2]$ 有周期 3（ $T[2]=T[5]=3$ ， $T[3]=T[6]=2$ ），非本原，跳过
最终：

dp_6 = dp_5 + dp_4 + dp_3 + dp_0 = 10 + 7 + 4 + 1 = \boxed{22}

直觉总结
每一步的逻辑可以这样理解：

要计算 $dp_i$ ，我们枚举"最后一段"的长度 $L$ ，即 $T[i-L+1..i]$ 。
如果这一段是本原的（没有更短的周期），它产生的结果是"全新的"，不会和其他长度的最后一段重复。贡献 $dp_{i-L}$ 。
如果这一段非本原（有周期 $d < L$ ），说明它的效果能被更短的最后一段完全覆盖——直觉上，多余的"重复部分"可以被吸收进前缀中用另一种合法切法表达。所以跳过，避免重复计数。
不同的本原最后一段之间绝不产生重复：若两个本原段产生了相同结果，较长的那个就会出现周期，与本原性矛盾。
所以整个 DP 既不遗漏也不重复，恰好精确计数。

能不能使用样例，让我理解所谓的本源，以及为什么周期为 len 才可以贡献？不为 len 就不能贡献？把这个讲清楚。

好的，我用样例 1（ $T = [1, 1, 2, 1]$ ）来把这件事彻底讲清楚。

一、什么是"本原"

子串 $T[j+1..i]$ 是本原的，就是说它不存在比自身长度更短的周期。
具体几个例子（都来自样例 1）：

$T[3..4] = [2, 1]$ ： $T[3] \ne T[4]$ （ $2 \ne 1$ ），没有周期 1。最小周期 $= 2 =$ 长度。本原。
$T[1..2] = [1, 1]$ ： $T[1] = T[2] = 1$ ，有周期 1 $< 2$ 。非本原。
$T[2..4] = [1, 2, 1]$ ： $T[2] = T[4] = 1$ ，有周期 2 $< 3$ 。非本原。
$T[1..4] = [1, 1, 2, 1]$ ： $T[1] = T[4] = 1$ ，有周期 3 $< 4$ 。非本原。

二、非本原段为什么不贡献——用具体例子看"冗余"

例子 A： $T[2..4] = [1, 2, 1]$ ，周期 2，非本原

我们在计算 $dp_4$ 时，考虑最后一段 $[2, 4]$ （ $L=3$ ， $j=1$ ）。
用 $[2,4]$ 做最后一段时：

位置 2, 3, 4 的值 $=$ $\text{rev}(T[2..4]) = [T[4], T[3], T[2]] = [1, 2, 1]$
前缀 $T[1..1]$ 只有 $dp_1 = 1$ 种结果 $= [1]$
唯一产生的完整结果： $[1] \circ [1, 2, 1] = [\mathbf{1, 1, 2, 1}]$
现在我来证明，这个结果已经被更短的最后一段覆盖了。
用 $[4,4]$ 做最后一段（ $L=1$ ， $j=3$ ）：
位置 4 的值 $= T[4] = 1$
前缀 $T[1..3]$ 有 $dp_3 = 3$ 种结果
$T[1..3] = [1,1,2]$ 的 3 种结果之一：用分段 $\{[1,1],[2,2],[3,3]\}$ ，得 $[1, 1, 2]$ 。
拼起来： $[1, 1, 2] \circ [1] = [\mathbf{1, 1, 2, 1}]$ —— 和上面一模一样！
所以最后一段 $[2,4]$ 的唯一贡献 $[1,1,2,1]$ 已经被最后一段 $[4,4]$ 包含了。如果我们同时计算两者，就会重复计数。
为什么这行得通？ 关键就在周期。 $T[2..4]$ 有周期 2，意味着 $T[2] = T[4]$ 。
对比两种最后一段在位置 4 上的表现：
最后一段 $[2,4]$ ：位置 4 得到的是 $T[2] = 1$ （翻转后，段首跑到段尾）
最后一段 $[4,4]$ ：位置 4 得到的是 $T[4] = 1$
$T[2] = T[4]$ 正是周期条件保证的！ 这使得位置 4 的值一致。而被"多出来"的位置 2, 3 则可以交给前缀去处理——用 $T[1..3]$ 的某种分段来产生需要的 $[1, 1, 2]$ 。

例子 B： $T[1..4] = [1, 1, 2, 1]$ ，周期 3，非本原

用 $[1,4]$ 做最后一段（整段翻转）：

结果 $= \text{rev}(T[1..4]) = [T[4], T[3], T[2], T[1]] = [1, 2, 1, 1]$
这能被更短的最后一段覆盖吗？周期 $d=3$ ，所以对应更短的最后一段 $[1+3, 4] = [4, 4]$ 。
用 $[4,4]$ 做最后一段：
位置 4 $= T[4] = 1$
需要前缀 $= [1, 2, 1]$
$T[1..3]=[1,1,2]$ 能产生 $[1,2,1]$ 吗？用分段 $\{[1,1], [2,3]\}$ ： $[1] \circ \text{rev}([1,2]) = [1] \circ [2, 1] = [1, 2, 1]$ 。可以！
拼起来： $[1, 2, 1] \circ [1] = [\mathbf{1, 2, 1, 1}]$ —— 又是同一个结果！
核心机理相同： $T[1..4]$ 有周期 3，意味着 $T[1] = T[4] = 1$ 。所以位置 4 上：长段给出 $T[1]=1$ ，短段给出 $T[4]=1$ ，一致。多出来的位置 1, 2, 3 交给前缀来处理。

三、本原段为什么能贡献——它的结果是"全新的"

例子 C： $T[3..4] = [2, 1]$ ，本原

用 $[3,4]$ 做最后一段（ $L=2$ ， $j=2$ ）：

位置 3, 4 $= \text{rev}(T[3..4]) = [T[4], T[3]] = [1, 2]$
前缀 $T[1..2]$ 有 $dp_2 = 1$ 种结果 $= [1, 1]$
唯一结果： $[1, 1] \circ [1, 2] = [\mathbf{1, 1, 1, 2}]$
这个结果能不能被最后一段 $[4,4]$ （ $L=1$ ）覆盖？
用 $[4,4]$ ：位置 4 $= T[4] = \mathbf{1}$ 。
但我们需要位置 4 $= \mathbf{2}$ （来自 $[3,4]$ 翻转后的 $T[3]=2$ ）。
$1 \ne 2$ ，不可能！ 所以 $[1,1,1,2]$ 绝不可能从最后一段 $[4,4]$ 产生。
根本原因：要想让 $[3,4]$ 和 $[4,4]$ 在位置 4 上给出相同的值，需要 $T[3] = T[4]$ （即周期 1）。但 $T[3]=2 \ne T[4]=1$ 。 $[2,1]$ 是本原的，没有周期 1。所以两种最后一段在位置 4 上必然给出不同的值，从而产生不同的结果。

四、总结原理

对于最后一段 $T[j+1..i]$ （长度 $L$ ），考虑"更短一截"的最后一段 $T[j+d+1..i]$ （长度 $L-d$ ）：
两者在位置 $j+d+1$ 到 $i$ 的重叠区域上：

长段 $[j+1, i]$ 翻转后，位置 $p$ 得到 $T[i+j+1-p]$
短段 $[j+d+1, i]$ 翻转后，位置 $p$ 得到 $T[i+j+d+1-p]$
两者相等要求：

T[i+j+1-p] = T[i+j+d+1-p] \quad \text{即} \quad T[q] = T[q+d]

这恰好就是周期 $d$ 的定义！
所以：

有周期 $d < L$ （非本原） $\Rightarrow$ 重叠区域值完全一致 $\Rightarrow$ 多出来的 $d$ 个位置可以交给前缀处理 $\Rightarrow$ 长段的所有结果都被短段覆盖 $\Rightarrow$ 不贡献（计入则重复）
没有任何周期 $d < L$ （本原） $\Rightarrow$ 对任何更短的段，重叠区域上至少有一个位置值不同 $\Rightarrow$ 结果一定不同 $\Rightarrow$ 贡献是全新的
这就是为什么 DP 转移中只统计本原段：本原 = 不可替代 = 贡献新结果，非本原 = 可以被更短段覆盖 = 已经被计算过了。

我怎么样通过一种比较好的数学运算方法，运算分段 rev 和整体 rev 是否相同？

这个问题有一个非常优雅的数学观察。

核心：交换两块

设在 $T[l..r]$ 中，切点在 $m$ 。令：

A = \text{rev}(T[l..m]), \quad B = \text{rev}(T[m+1..r])

那么：

分段翻转的结果 $= A \circ B$ （先放 $A$ 再放 $B$ ）
整体翻转的结果 $= \text{rev}(T[l..r]) = B \circ A$ （这是翻转拼接的标准性质： $\text{rev}(XY) = \text{rev}(Y)\text{rev}(X)$ ）
所以问题变成：

A \circ B = B \circ A \quad ?

即：两个字符串是否在拼接运算下交换。

字符串交换的经典定理

有一个经典结论：

两个非空字符串 $A$ 和 $B$ 满足 $AB = BA$ ，当且仅当存在一个字符串 $Z$ ，使得 $A = Z^p$ ， $B = Z^q$ （ $p, q \ge 1$ ）。
也就是说， $A$ 和 $B$ 必须都是同一个基本串的若干次重复。

用具体例子感受

例子 1： $T[1..4] = [1, 2, 1, 2]$ ，切点 $m=2$ 。

A = \text{rev}([1,2]) = [2,1], \quad B = \text{rev}([1,2]) = [2,1]

$A = B = [2,1]$ ，显然 $AB = BA$ 。（ $Z = [2,1]$ ， $p = q = 1$ ）
验证：分段翻转 $= [2,1,2,1]$ ，整体翻转 $= \text{rev}([1,2,1,2]) = [2,1,2,1]$ 。相等 ✓
例子 2： $T[2..4] = [1, 2, 1]$ （样例 1 中），切点 $m=3$ 。

A = \text{rev}([1,2]) = [2,1], \quad B = \text{rev}([1]) = [1]

$AB = [2,1,1]$ ， $BA = [1,2,1]$ 。 $AB \ne BA$ 。
$A=[2,1]$ 和 $B=[1]$ 不是同一个基本串的幂次（因为长度 2 和 1 的公共基本串只能长度 1，那就要求 $A = [c, c]$ ，但 $A=[2,1]$ ），所以不交换 ✓
例子 3： $T = [1,2,1,2,1,2]$ ，切点 $m=2$ 。

A = \text{rev}([1,2]) = [2,1], \quad B = \text{rev}([1,2,1,2]) = [2,1,2,1]

$Z = [2,1]$ ， $A = Z^1$ ， $B = Z^2$ 。所以 $AB = BA$ 。
验证： $AB = [2,1,2,1,2,1]$ ， $BA = [2,1,2,1,2,1]$ 。相等 ✓

等价的周期条件

$AB = BA$ 也可以翻译成周期语言：
设 $a = |A| = m - l + 1$ ， $b = |B| = r - m$ 。则：

AB = BA \iff T[l..r] \text{ 有周期 } \gcd(a, b)

这是因为"两块能交换"等价于整个串由一个长度为 $\gcd(a,b)$ 的基本单元循环构成。

实际计算方法

在代码中，判断"分段 rev $=$ 整体 rev"最实用的方式是字符串哈希：
对 $T$ 预处理多项式哈希（前缀哈希 + 逆序前缀哈希），就可以 $O(1)$ 比较任意子串、翻转子串。具体地：

计算 $\text{hash}(AB)$ ：用 $A$ 的哈希和 $B$ 的哈希拼接
计算 $\text{hash}(BA)$ ：用 $B$ 的哈希和 $A$ 的哈希拼接
两者相等则分段 rev $=$ 整体 rev
或者更直接地：检查 $T[j] = T[j + b]$ 对所有 $l \le j \le m$ 是否成立（周期 $b$ 条件），同时检查 $T[j] = T[j + a]$ 对所有 $l \le j \le l+b-1$ 是否成立（周期 $a$ 条件）。两个条件都满足才行。

总结：分段翻转和整体翻转是否相同，本质上就是问两个翻转后的块能否交换顺序，即 $AB \stackrel{?}{=} BA$ 。这当且仅当 $A$ 和 $B$ 是同一个基本串的幂次，也等价于整个子串有周期 $\gcd(|A|, |B|)$ 。

P4391 [BalticOI 2009] Radio Transmission 无线传输

计算这个串的周期所使用的这个哈希做法。

首先呢，计数问题，还是要选择 dp 解决。

Gemini 的回答

问题转化
由于翻转操作是对称的，将初始数组 $S$ 划分为若干段并分别翻转得到目标数组 $T$ ，完全等价于将 $T$ 按照完全相同的划分方式进行分别翻转，从而得到 $S$ 。因此，原问题可以转化为：对于给定的数组 $T$ ，将其划分为任意个连续子段并分别翻转，能够产生多少种不同的数组 $S$ 。
分析重复情况与核心结论
如果我们随意对 $T$ 进行划分并计算结果，会遇到“不同的划分方式产生相同数组 $S$ ”的情况。
例如，设当前段为 [1, 2, 3, 1]，如果将其作为一整段翻转，会得到 [1, 3, 2, 1]；但如果我们将其划分为 [1]、[2, 3]、[1] 三段分别翻转，拼起来的结果依然是 [1, 3, 2, 1]。
发生这种等价替换的根本原因在于：当某一段序列存在一个“前缀等于后缀”（在字符串理论中被称为 Border）时，对其整体翻转的结果，必定等价于将其拆分为更小块分别翻转的结果。
可以证明，为了避免重复计数，我们只需要在所有的划分方案中，只统计那些所有子段都“无 Border”的划分。无 Border 的定义是：对于长度为 $L$ 的子段，不存在一个长度介于 $1$ 到 $L-1$ 之间的前缀，与相同长度的后缀完全相等。
任意一个能够通过翻转生成的合法数组 $S$ ，都存在且唯一存在一种完全由“无 Border”子段构成的划分方案。因此，所求的合法数组 $S$ 的数量，恰好就等于将数组 $T$ 划分为若干个“无 Border”子段的合法方案数。
动态规划设计
基于上述结论，我们可以使用一维动态规划来解决。
定义 dp[i] 表示将数组 $T$ 的前 $i$ 个元素划分为若干个无 Border 子段的方案数。
初始化时 dp[0] = 1，其余为 $0$ 。
当我们要从状态 dp[i] 向后转移时，我们需要寻找所有合法的右端点 $j$ 。条件就是：从 $i+1$ 到 $j$ 构成的子段必须是无 Border 的。如果满足，则执行状态转移：
dp[j] = (dp[j] + dp[i]) % 998244353
借助 KMP 算法加速判断
如何快速判断区间是否存在 Border？这恰好是 KMP 算法中求解前缀函数 pi 数组的核心作用。
pi[k] 存储的是前缀子串中最长的“真前缀等于真后缀”的长度。如果 pi[k] == 0，就意味着当前这一段子串不存在任何 Border。
因此，我们可以这样做：

外层循环枚举划分的左端点 $i$ （从 $0$ 到 $n-1$ ）。
如果 dp[i] == 0，直接跳过以优化常数。
否则，将 $T$ 从 $i+1$ 到 $n$ 的剩余部分作为一个新的模式串，对其运行 KMP 算法求解 pi 数组。
在计算 pi 数组的过程中，对于当前长度 $k$ ，只要发现对应的 pi 值为 $0$ ，就说明从 $i+1$ 开始、长度为 $k$ 的这一段是无 Border 的，立刻将 dp[i] 的值累加到对应的 dp[i + k] 上即可。
复杂度分析
外层遍历左端点 $i$ ，共执行 $n$ 次。每次针对剩余后缀计算 pi 数组时，KMP 算法的复杂度为线性的 $O(n-i)$ 。
因此整体的时间复杂度为 $O(n^2)$ 。题目给定的所有测试用例的 $n$ 之和 $\sum n \le 8000$ ，其平方规模在 $6 \times 10^7$ 左右，在 2 秒的时限内可以非常高效地通过。空间复杂度仅需维护 dp 数组和单次 KMP 的 pi 数组，为 $O(n)$ 。

不过总体上来说，我们对 border 的概念不是很熟。

确实，这道题目的难点就在于，对于不同的划分，如果有相同的这个答案怎么办？这个时候就需要引入字符串算法。

Border 的具体性质以及解释

Border 的定义
在序列（如字符串或数组）中，如果该序列的一个非平凡前缀（即长度大于 $0$ 且小于序列总长度的前缀）和它的一个非平凡后缀完全相同，那么这个相同的前缀或后缀就被称为该序列的一个 Border。
举个具体的例子：考虑数组 [1, 2, 4, 5, 1, 2]。
这个数组长度为 $6$ 。取它的前缀 [1, 2]，再取它的后缀 [1, 2]，两者完全相同。因此，[1, 2] 就是这个数组的一个 Border。
Border 对计数产生重复的具体机制
题目要求我们计算能生成多少种不同的初始数组 $S$ 。如果我们在动态规划中不加任何限制，直接枚举所有可能的划分方式，就会把“产生相同最终数组的不同划分方式”重复计算。
我们继续以数组 [1, 2, 4, 5, 1, 2] 为例。假设它是目标数组 $T$ 里的某一个连续子段。现在我们要对这一段进行划分并分别翻转。观察以下两种截然不同的划分方式：
划分方案一：作为一个整体翻转
我们将 [1, 2, 4, 5, 1, 2] 视为单独的一大段，整体进行一次翻转操作。
翻转后的结果是：[2, 1, 5, 4, 2, 1]。
划分方案二：沿着 Border 将其拆分后分别翻转
我们把这段数组拆分成三小段，分别是：前缀 Border、中间剩余的部分、后缀 Border，即拆分为 [1, 2]、[4, 5]、[1, 2]。
我们对这三个小段分别独立进行翻转：
第一段 [1, 2] 翻转得到 [2, 1]；
第二段 [4, 5] 翻转得到 [5, 4]；
第三段 [1, 2] 翻转得到 [2, 1]。
最后，把这三段翻转后的结果原样拼接起来，得到的结果依然是：[2, 1, 5, 4, 2, 1]。
可以看出，不同的划分方式（整体分 $1$ 段对比拆分成 $3$ 段）最终产生了一模一样的生成数组。如果不加干预，这两种划分方案都会被统计入总方案数中，对于同一个合法的数组 $S$ ，我们就进行了重复计数。
将现象抽象化
为什么只要存在 Border 就会发生这种情况？
我们可以把任意存在 Border 的序列抽象地表示为 $B + M + B$ （其中 $B$ 是 Border 代表的子段， $M$ 是中间夹着的子段， $+$ 表示拼接操作）。
如果我们把它作为整体翻转，得到的是 $(B + M + B)^R$ 。根据翻转操作的数学性质，把一个拼接序列整体翻转，等价于把原序列从后往前依次翻转拼接，即结果为 $B^R + M^R + B^R$ 。
如果我们把它拆分成三段分别翻转并拼接，结果显然也是 $B^R + M^R + B^R$ 。
这就推导出了一个核心结论：只要某一段序列内部存在 Border，那么把这段序列“整体翻转”所产生的效果，总是可以被“沿着 Border 切分成更小的块并分别翻转”的效果完全替代。
消除重复的最终策略
既然“存在 Border 的大段”总是可以被等价替换为“没有 Border 的小段组合”，那么为了做到不重不漏，我们需要为每一种生成的最终数组 $S$ 寻找一个唯一代表它的划分方式。
我们的强制规定就是：在所有能产生同一个结果 $S$ 的划分方案中，我们只统计那种“被拆分得最细”的方案。
什么样的方案是拆得最细的？就是划分出来的每一小段序列，都不存在任何 Border。
因为一旦某个子段没有 Border，它就绝对无法再被拆解为类似于 $B + M + B$ 的形式，也就意味着它“作为一个整体翻转产生的结果”，绝对无法通过“拆分成更小的几段分别翻转”来伪造。
可以从数学上严谨证明，任意一个能够通过翻转操作生成的合法数组 $S$ ，都存在且仅存在一种完全由“无 Border 子段”构成的划分方式。因此，只要在动态规划转移时，严格限制划分出来的每一段都必须没有 Border，我们计算出的方案数就恰好等于最终生成的不同数组 $S$ 的数量，从而达到了去重目的的不同数组 $S$ 的数量。

Gemini 的算法对样例的模拟演示

好的，我们对样例 `6 \\n 1 3 2 3 3 2` 进行详细的算法模拟。
目标数组 $T = [1, 3, 2, 3, 3, 2]$ ，长度 $n = 6$ 。
我们使用一维 DP，`dp[i]` 表示将 $T$ 的前 $i$ 个元素划分为若干个无 Border 子段的方案数。
初始化：`dp[0] = 1`，其余 `dp[1...6] = 0`。

第一步：以 $i = 0$ 为左端点进行拓展

当前 dp[0] = 1。我们需要考察从下标 $1$ 开始的后缀 $T[1...6] = [1, 3, 2, 3, 3, 2]$ 。
对此后缀运行 KMP 求 pi 数组（注：为方便描述，这里子串内索引用 $1$ 开始，对应原数组 $T$ 的前缀长度 $k$ ）：

长度 $k$	当前子串	KMP `pi[k]`	`pi[k] == 0`?	DP 转移操作
$1$	`[1]`	$0$	是	`dp[1] += dp[0]` $\rightarrow$ `dp[1] = 1`
$2$	`[1, 3]`	$0$	是	`dp[2] += dp[0]` $\rightarrow$ `dp[2] = 1`
$3$	`[1, 3, 2]`	$0$	是	`dp[3] += dp[0]` $\rightarrow$ `dp[3] = 1`
$4$	`[1, 3, 2, 3]`	$0$	是	`dp[4] += dp[0]` $\rightarrow$ `dp[4] = 1`
$5$	`[1, 3, 2, 3, 3]`	$0$	是	`dp[5] += dp[0]` $\rightarrow$ `dp[5] = 1`
$6$	`[1, 3, 2, 3, 3, 2]`	$0$	是	`dp[6] += dp[0]` $\rightarrow$ `dp[6] = 1`
本轮结束状态：`dp = [1, 1, 1, 1, 1, 1, 1]`

第二步：以 $i = 1$ 为左端点进行拓展

当前 dp[1] = 1。考察从下标 $2$ 开始的后缀 $T[2...6] = [3, 2, 3, 3, 2]$ 。

长度 $k$	当前子串	KMP `pi[k]`	`pi[k] == 0`?	DP 转移操作
$1$	`[3]`	$0$	是	`dp[1+1] += dp[1]` $\rightarrow$ `dp[2] = 2`
$2$	`[3, 2]`	$0$	是	`dp[1+2] += dp[1]` $\rightarrow$ `dp[3] = 2`
$3$	`[3, 2, 3]`	$1$ (Border:`[3]`)	否	无操作
$4$	`[3, 2, 3, 3]`	$1$ (Border:`[3]`)	否	无操作
$5$	`[3, 2, 3, 3, 2]`	$2$ (Border:`[3, 2]`)	否	无操作
本轮结束状态：`dp = [1, 1, 2, 2, 1, 1, 1]`

第三步：以 $i = 2$ 为左端点进行拓展

当前 dp[2] = 2。考察从下标 $3$ 开始的后缀 $T[3...6] = [2, 3, 3, 2]$ 。

长度 $k$	当前子串	KMP `pi[k]`	`pi[k] == 0`?	DP 转移操作
$1$	`[2]`	$0$	是	`dp[2+1] += dp[2]` $\rightarrow$ `dp[3] = 4`
$2$	`[2, 3]`	$0$	是	`dp[2+2] += dp[2]` $\rightarrow$ `dp[4] = 3`
$3$	`[2, 3, 3]`	$0$	是	`dp[2+3] += dp[2]` $\rightarrow$ `dp[5] = 3`
$4$	`[2, 3, 3, 2]`	$1$ (Border:`[2]`)	否	无操作
本轮结束状态：`dp = [1, 1, 2, 4, 3, 3, 1]`

第四步：以 $i = 3$ 为左端点进行拓展

当前 dp[3] = 4。考察从下标 $4$ 开始的后缀 $T[4...6] = [3, 3, 2]$ 。

长度 $k$	当前子串	KMP `pi[k]`	`pi[k] == 0`?	DP 转移操作
$1$	`[3]`	$0$	是	`dp[3+1] += dp[3]` $\rightarrow$ `dp[4] = 7`
$2$	`[3, 3]`	$1$ (Border:`[3]`)	否	无操作
$3$	`[3, 3, 2]`	$0$	是	`dp[3+3] += dp[3]` $\rightarrow$ `dp[6] = 5`
本轮结束状态：`dp = [1, 1, 2, 4, 7, 3, 5]`

第五步：以 $i = 4$ 为左端点进行拓展

当前 dp[4] = 7。考察从下标 $5$ 开始的后缀 $T[5...6] = [3, 2]$ 。

长度 $k$	当前子串	KMP `pi[k]`	`pi[k] == 0`?	DP 转移操作
$1$	`[3]`	$0$	是	`dp[4+1] += dp[4]` $\rightarrow$ `dp[5] = 10`
$2$	`[3, 2]`	$0$	是	`dp[4+2] += dp[4]` $\rightarrow$ `dp[6] = 12`
本轮结束状态：`dp = [1, 1, 2, 4, 7, 10, 12]`

第六步：以 $i = 5$ 为左端点进行拓展

当前 dp[5] = 10。考察从下标 $6$ 开始的后缀 $T[6...6] = [2]$ 。

长度 $k$	当前子串	KMP `pi[k]`	`pi[k] == 0`?	DP 转移操作
$1$	`[2]`	$0$	是	`dp[5+1] += dp[5]` $\rightarrow$ `dp[6] = 22`
最终状态：`dp = [1, 1, 2, 4, 7, 10, 22]`

模拟结论

遍历结束后，我们将整个数组 $T$ （长度为 $6$ ）划分为若干个无 Border 子段的总方案数，即为 dp[6]。
模拟得出的 dp[6] 的值为 $22$ 。
对比题目样例：

1 2	6 1 3 2 3 3 2

样例输出恰好为 22。算法模拟过程严丝合缝地吻合了正确答案。

众所周知，计数题目，必须要找到一种方法，一种特征，保证符合这一特征的划分方式/方案之间是独立，互不相同的。这道题目的特征如下：（注意，我们认为单一字符符合这个要求，毕竟递归需要有一终止条件嘛）

只要有前后缀相同情况，那么一定会有更加细粒度的切分方法，实现相同效果。

不过，如果只是需要无前后缀相同情况的话，那么直接判断一下前后缀第一个一不一样不就行了？事实上，我们要求，我们所选择的串，其所有子串（长度 ≥ 2）的前后缀都必须不同。

Codeforces Round 1083 (Div. 2)——CF-2205-C. Simons and Posting Blogs

Posted on 2026-03-01 Edited on 2026-03-02

题目大意

题目描述

有 $n$ 篇博客，第 $i$ 篇博客按顺序提到了 $l_i$ 个用户，用数组 $a_i=[a_{i,1},a_{i,2},\dots,a_{i,l_i}]$ 表示。

你需要将这 $n$ 篇博客全部发布。维护一个序列 $Q$ （初始为空）来记录最近提到的用户列表。你需要选择一个所有 $n$ 篇博客的发布顺序进行发布，每次发布一篇博客 $i$ 时，会对每一个 $1 \le j \le l_i$ 依次执行以下操作：

如果 $a_{i,j}$ 已经存在于 $Q$ 中，则将 $a_{i,j}$ 移动到 $Q$ 的开头。
否则，将 $a_{i,j}$ 插入到 $Q$ 的开头。

求在发布所有 $n$ 篇博客后，所能得到的字典序最小的序列 $Q$ 。

输入格式

第一行包含一个整数 $t$ （ $1 \le t \le 1000$ ），表示测试用例的数量。
每个测试用例第一行包含一个整数 $n$ （ $1 \le n \le 3000$ ），表示博客数量。
接下来 $n$ 行，每行首先包含一个整数 $l_i$ （ $1 \le l_i \le 3000$ ），表示第 $i$ 篇博客提到的用户数量，随后跟着 $l_i$ 个整数 $a_{i,1},a_{i,2},\dots,a_{i,l_i}$ （ $1 \le a_{i,j} \le 10^6$ ），表示提到的用户列表。
保证所有测试用例中 $n$ 的总和不超过 $3000$ ， $\sum l_i$ 的总和不超过 $3000$ 。

输出格式

对于每个测试用例，输出一行包含若干个整数，表示能够得到的字典序最小的 $Q$ 。

样例数据

Input
5
3
5 1 2 3 4 6
3 2 5 1
4 1 9 2 3
2
2 1 6
1 6
1
3 6 1 1
5
4 2 3 3 4
5 1 2 4 3 1
2 4 1
3 3 3 1
5 4 3 2 2 2
5
4 2 3 1 4
5 2 5 5 6 5
5 3 4 7 5 5
8 3 6 4 3 1 1 5 4
2 1 1

Output
1 5 2 3 9 6 4
6 1
1 6
1 3 2 4
1 4 3 2 5 6 7

样例解释

在第一个测试用例中，可以按如下顺序发布博客：

发布第一篇博客， $Q$ 变为 $[6,4,3,2,1]$ 。
发布第三篇博客， $Q$ 变为 $[3,2,9,1,6,4]$ 。
发布第二篇博客， $Q$ 变为 $[1,5,2,3,9,6,4]$ 。

这里存在其他的发布方式，例如：

发布第三篇博客， $Q$ 变为 $[3,2,9,1]$ 。
发布第一篇博客， $Q$ 变为 $[6,4,3,2,1,9]$ 。
发布第二篇博客， $Q$ 变为 $[1,5,2,6,4,3,9]$ 。

可以看到 $[1,5,2,3,9,6,4]$ 的字典序比其他结果更小。如果我们不把第二篇博客放在最后发布，序列的第一个元素将不会是 $1$ 。因此 $[1,5,2,3,9,6,4]$ 就是能得到的字典序最小的数组 $Q$ 。

在第二个测试用例中，可以按如下顺序发布博客：

发布第一篇博客， $Q$ 变为 $[6,1]$ 。
发布第二篇博客， $Q$ 保持自身为 $[6,1]$ 。

在第三个测试用例中，只能发布唯一的一篇博客， $Q$ 会变为 $[1,6]$ 。

思路讲解

OPUS 4.6 的思路

这道题有一个比较干净的做法，不需要动态排序和复杂删除。核心在于把"逆序操作"的想法进一步转化成一个简单的贪心。
关键观察：如何理解最终的 Q
设发布顺序为 $\pi_1, \pi_2, \dots, \pi_n$ 。最终的 $Q$ 可以这样等价地构造：
按逆序发布顺序（即 $\pi_n, \pi_{n-1}, \dots, \pi_1$ ）依次处理每篇博客，对每篇博客从右往左扫描，遇到还没出现过的用户就追加到 $Q$ 末尾。
这是因为最后发布的博客决定了 $Q$ 最前面的部分（最近被移到前面的用户），倒数第二篇决定了下一段，以此类推。
预处理：有效序列
对每篇博客 $i$ ，从右往左扫描，保留每个用户的首次出现，得到"有效序列" $R_i$ 。例如博客 [1, 2, 1, 3] 的有效序列为 [3, 1, 2]。
贪心选择
维护一个集合 used 记录已经放入 $Q$ 的元素。每一步：

对每个还未选过的博客，把其有效序列中 used 里的元素跳过，得到"剩余有效序列"。
选择剩余有效序列字典序最小的博客。
把它的剩余有效序列追加到 $Q$ ，并将这些元素加入 used。
重复直到所有博客选完。
正确性（交换论证）：如果两个博客 $A$ 、 $B$ 的剩余有效序列满足 $A' < B'$ （字典序），那么先处理 $A$ 再处理 $B$ ， $Q$ 的前缀就是 $A'$ 开头，一定不劣于 $B'$ 开头。当 $A'$ 是 $B'$ 的前缀时，两种顺序结果相同，不影响。
用第一个样例验证
博客有效序列：

博客 1：[6, 4, 3, 2, 1]
博客 2：[1, 5, 2]
博客 3：[3, 2, 9, 1]
第一步：博客 2 的 [1, 5, 2] 字典序最小（以 1 开头），选它。 $Q = [1, 5, 2]$ 。
第二步：博客 1 剩余 [6, 4, 3]，博客 3 剩余 [3, 9]。选博客 3（3 < 6）。 $Q = [1, 5, 2, 3, 9]$ 。
第三步：博客 1 剩余 [6, 4]。 $Q = [1, 5, 2, 3, 9, 6, 4]$ 。与期望答案完全一致。
复杂度
时间 $O(L^2)$ ，其中 $L = \sum l_i \le 3000$ 。空间 $O(L)$ 。只需要一个哈希集合来判断元素是否已使用，不需要任何平衡树、动态排序等复杂结构。

哎，其实这个思路和我一模一样，这个思路其实和我一模一样，我说白了你不会更加有更加简单的做法，实际上你就是这个做法，绷不住了。

也看了各路大神的代码，确实是没有更加简单的做法了。

while (!g.empty()) {
    sort(all(g));
    for (auto a:g[0]) {
        ans.push_back(a);
        used.insert(a);
    }
    vector<vector<ll>> new_g;
    for (int i=1;i<g.size();++i) {
        new_g.push_back(gen_uni(g[i]));
    }
    swap(new_g,g);
}

AC代码

AC
http://codeforces.com/contest/2205/submission/365031780

源代码

/**
 * Problem: C. Simons and Posting Blogs
 * Contest: Codeforces Round 1083 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2205/problem/C
 * Created: 2026-02-28 22:53:22
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */

void Solve() {
    ll N;
    cin >> N;
    vector<vector<ll>> g(N);
    for (int i=0;i<N;++i) {
        ll sz;
        cin>>sz;
        g[i].resize(sz);
        for (int j=0;j<sz;++j) {
            ll u;
            cin>>u;
            g[i][j]=u;
        }
        reverse(all(g[i]));
        vector<ll> b;
        set<ll> st;
        for (auto a:g[i]) {
            if (st.contains(a)) {
                continue;
            }
            b.push_back(a);
            st.insert(a);
        }
        swap(g[i],b);
    }
    set<ll> used;
    auto gen_uni=[&](const vector<ll> & vec) -> vector<ll> {
        vector<ll> res;
        for (auto a:vec) {
            if (used.contains(a)) {
                continue;
            }
            res.push_back(a);
        }
        return res;
    };
    vector<ll> ans;
    while (!g.empty()) {
        sort(all(g));
        for (auto a:g[0]) {
            ans.push_back(a);
            used.insert(a);
        }
        vector<vector<ll>> new_g;
        for (int i=1;i<g.size();++i) {
            new_g.push_back(gen_uni(g[i]));
        }
        swap(new_g,g);
    }
    for (auto a:ans) {
        cout<<a<<" ";
    }
    cout<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
http://codeforces.com/contest/2205/submission/365031780

*/

心路历程（WA，TLE，MLE……）

Codeforces Round 1083 (Div. 2)——CF-2205-D. Simons and Beating Peaks（笛卡尔树）

Posted on 2026-03-01 Edited on 2026-03-02

题目大意

题目描述

定义一个长度为 $m$ 的数组 $b$ 是“好的”，当且仅当不存在任何索引 $i$ （ $1 < i < m$ ）满足 $b_i = \max(\{b_{i-1}, b_i, b_{i+1}\})$ 。

给定一个长度为 $n$ 的排列 $a$ 。如果数组不是“好的”，你可以反复执行以下操作：
选择一个满足 $a_i = \max(\{a_{i-1}, a_i, a_{i+1}\})$ 的索引 $i$ （ $1 < i < n$ ）。然后，你可以从数组中删除 $a_{i-1}$ 或 $a_{i+1}$ 。删除后，数组的左右两部分会重新拼接在一起。

求出使初始排列 $a$ 变为“好的”所需的最小操作次数。

输入格式

第一行包含一个整数 $t$ （ $1 \le t \le 5 \cdot 10^4$ ），表示测试用例的数量。

对于每个测试用例：
第一行包含一个整数 $n$ （ $3 \le n \le 5 \cdot 10^5$ ），表示排列的长度。
第二行包含 $n$ 个互不相同的整数 $a_1, a_2, \ldots, a_n$ （ $1 \le a_i \le n$ ），表示初始的排列。

保证所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^5$ 。

输出格式

对于每个测试用例，输出一个整数，表示使数组变为“好的”所需的最小操作次数。

样例

输入

5
3
1 2 3
5
4 1 3 2 5
6
4 5 3 6 2 1
7
6 5 1 7 4 2 3
15
7 4 10 12 9 14 5 3 8 11 1 15 2 13 6

输出

样例解释

在第一组测试用例中，数组初始时已经是“好的”，因此不能执行任何操作，答案为 $0$ 。

在第二组测试用例中，可以进行如下操作：
选择索引 $3$ ，此时满足 $a_3 = \max(\{a_2, a_3, a_4\})$ （即 $3 = \max(\{1, 3, 2\})$ ）。接着从数组中移除 $a_2$ （元素 $1$ ）。数组变为 $[4, 3, 2, 5]$ 。
此时数组已经是“好的”，因此答案为 $1$ 。

在第三组测试用例中，可以进行如下操作：
选择索引 $2$ 。从数组中移除 $a_1$ 。数组变为 $[5, 3, 6, 2, 1]$ 。
选择索引 $3$ 。从数组中移除 $a_2$ 。数组变为 $[5, 6, 2, 1]$ 。
选择索引 $2$ 。从数组中移除 $a_1$ 。数组变为 $[6, 2, 1]$ 。
通过上述 $3$ 次操作，数组变为“好的”。

思路讲解

官方解法是这个笛卡尔树，不过我不太会这个东西，我们来看看其他做法吧。

https://www.luogu.com.cn/article/h4sddubz

这个 luogu 题解抓住了最大值一定不会被删除这个特性。（并不是删除最大值不优秀，而是重新阅读题面，你会发现）

luogu 题解递归式求解做法（我感觉挺好的）

题解：CF2205D Simons and Beating Peaks
注意到，数组的最大值必须置于两端。否则，我们必须将其左侧或右侧的所有元素全部删除，然后得到一个新的子数组。每次操作都会导致区间的缩小，因而可以递归求解。
具体地，对于区间 $[l, r]$ ，如果 $a_x = \max_{l \le i \le r} a_i$ ，那么我们有两种选择：

删去下标在 $l \sim x - 1$ 内的所有元素，区间缩小为 $[x + 1, r]$ 。
删去下标在 $x + 1 \sim r$ 内的所有元素，区间缩小为 $[l, x - 1]$ 。
因此，递推式为：

f_{l, r} = \min(r - x + f_{l, x - 1}, x - l + f_{x + 1, r})

如果暴力求解区间最大值，那么平均复杂度为 $O(n \log n)$ ，但若原数组单调，则会被卡成 $O(n^2)$ 。
故考虑用 ST 表维护区间最大值，递归过程可优化至 $O(n)$ 。
时间复杂度为 $O(\sum n \log n)$ ，瓶颈在 ST 表的初始化。

#include <bits/stdc++.h>
using namespace std;
int t, n, a[500001], pos[500001], st[500001][19];
int query(int l, int r) {
    int j = __lg(r - l + 1);
    return max(st[l][j], st[r-(1<<j)+1][j]);
}
int solve(int l, int r) {
    if (r - l <= 1) return 0;
    int x = pos[query(l,r)];
    return min(r - x + solve(l, x - 1), x - l + solve(x + 1, r));
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            pos[a[i]] = i;
        }
        for (int i = 1; i <= n; i++) st[i][0] = a[i];
        for (int j = 1; (1 << j) <= n; j++)
            for (int i = 1; i + (1 << j) - 1 <= n; i++) 
                st[i][j] = max(st[i][j-1], st[i+(1<<(j-1))][j-1]);
        cout << solve(1, n) << '\n';
    }
    return 0;
}

笛卡尔树

引入

笛卡尔树是一种二叉树，每一个节点由一个键值二元组 $(k, w)$ 构成。要求 $k$ 满足二叉搜索树（BST）的性质，而 $w$ 满足堆的性质。如果笛卡尔树的 $k, w$ 键值确定，且 $k$ 互不相同， $w$ 也互不相同，那么这棵笛卡尔树的结构是唯一的。如下图：

（图源自维基百科）
上面这棵笛卡尔树相当于把数组元素值当作键值 $w$ ，而把数组下标当作键值 $k$ 。可以发现，这棵树的键值 $k$ 满足 BST 的性质，而键值 $w$ 满足小根堆的性质。同时根据二叉搜索树的性质，可以发现这种特殊的笛卡尔树满足一棵子树内的下标是一个连续区间。
竞赛中使用笛卡尔树时，常用数组下标作为二元组的键值 $k$ ，数组下标 $k$ 满足 BST 性质。
下文使用 $k, w$ 时，默认 $k$ 满足 BST 性质， $w$ 满足堆的性质。

单调栈构建笛卡尔树

过程

我们考虑将元素按 $k$ 升序依次插入到当前的笛卡尔树中。
对于一棵笛卡尔树，定义「右链」为从根节点开始一直走右儿子，走到叶节点形成的链。则插入节点后，这个节点一定在右链上。因为是按照满足 BST 性质的 $k$ 升序插入，那么这个新插入的节点必然在树的最右端。这个节点不可能是一个左儿子，也没有右儿子。
于是我们执行这样一个过程，从下往上比较右链节点与当前节点 $u$ 的 $w$ ，如果找到了一个右链上的节点 $x$ 满足 $w_x < w_u$ ，就把 $u$ 接到 $x$ 的右儿子上，而 $x$ 原本的右子树就变成 $u$ 的左子树。
图中红框部分就是我们始终维护的右链：

显然每个数最多进出右链一次（或者说每个点在右链中存在的是一段连续的时间）。这个过程可以用单调栈维护，栈中维护当前笛卡尔树的右链上的节点。一个点不在右链上了就把它弹掉。这样每个点最多进出一次，复杂度 $O(n)$ 。

笛卡尔树与 Treap

实际上，Treap 是笛卡尔树的一种，只不过 Treap 中 $w$ 的值完全随机。Treap 有线性的构建算法，如果提前将键值 $k$ 排好序，是可以使用上述单调栈算法完成构建过程的，只不过很少会这么用。

C++ 实现

// stk 维护笛卡尔树中节点对应到序列中的下标
for (int i = 1; i <= n; i++) {
  int k = top;  // top 表示操作前的栈顶，k 表示当前栈顶
  while (k > 0 && w[stk[k]] > w[i]) k--;  // 维护右链上的节点
  if (k) rs[stk[k]] = i;  // 栈顶元素.右儿子 := 当前元素
  if (k < top) ls[i] = stk[k + 1];  // 当前元素.左儿子 := 上一个被弹出的元素
  stk[++k] = i;                     // 当前元素入栈
  top = k;
}

AI 总结的笛卡尔树式解法

一、笛卡尔树是什么

笛卡尔树（Cartesian Tree）是一种由序列构造出的二叉树，同时满足两个性质：

堆性质：每个子树的根节点是该子树中所有元素的最大值（大根笛卡尔树）或最小值（小根笛卡尔树）。
中序遍历性质：对树做中序遍历，得到的恰好是原序列。

构造方式（以大根笛卡尔树为例）

对于序列 $a_1, a_2, \ldots, a_n$ ：

根：整个序列的最大值 $a_p$ 。
左子树：由 $a_1, \ldots, a_{p-1}$ （最大值左边的部分）递归构造。
右子树：由 $a_{p+1}, \ldots, a_n$ （最大值右边的部分）递归构造。
以题目的样例 [4, 5, 3, 6, 2, 1] 为例：

          6(pos=4)
         / \\
   5(pos=2)  2(pos=5)
      / \\       \\
4(pos=1) 3(pos=3) 1(pos=6)

根是 6（全局最大），位置 4
左半 [4, 5, 3] 的最大值是 5（位置 2），成为左子树根
右半 [2, 1] 的最大值是 2（位置 5），成为右子树根
依此递归
核心直觉：笛卡尔树刻画了"每个区间的最大值把该区间分成左右两半"这一递归分治结构。

二、为什么这道题和笛卡尔树有关

第一步：理解"cool"数组的结构

“cool"数组要求没有内部峰值（即没有任何内部元素同时大于左右邻居）。由于元素互不相同，一个没有内部峰值的数组只能是先递减、再递增的"V 形”：

a_{i_1} > a_{i_2} > \cdots > a_{i_k} < a_{i_{k+1}} < \cdots < a_{i_m}

（递减或递增部分可以为空，即纯递增、纯递减也合法。）
如果序列中间出现了一个"先升后降"的拐点，那个拐点就是一个峰值，违反 cool 条件。

第二步：全局最大值 $n$ 必定保留且在端点

每次操作是"选一个峰 $a_i$ ，删掉 $a_{i-1}$ 或 $a_{i+1}$ "。被删除的只能是峰的邻居，而不是峰本身。全局最大值 $n$ 永远不可能是某个峰的邻居（因为没有比它更大的元素），所以 $n$ 永远不会被删除。
既然 $n$ 一定留在最终数组中，而最终数组是 V 形的，那么 $n$ 作为最大值如果出现在内部，它一定是峰值——矛盾。所以 $n$ 必须在最终数组的左端点或右端点。

第三步：递归结构 = 笛卡尔树

假设 $n$ 在位置 $p$ ：

$n$ 放左端点： $p$ 左边的所有元素全部删掉，只保留 $n$ + 右半部分的某个 V 形子序列。
$n$ 放右端点： $p$ 右边的所有元素全部删掉，只保留左半部分的某个 V 形子序列 + $n$ 。
无论哪种情况，问题递归到了 $n$ 的一侧。而那一侧的最大值（笛卡尔树对应子树的根）面临完全相同的约束——它也必须在该子问题最终数组的端点，否则它也是峰值。
这恰好是笛卡尔树的递归结构：

f(v) = 1 + \max\big(f(\text{左子树}),\; f(\text{右子树})\big)

其中 $f(v)$ 是以 $v$ 为根的子树中，能保留的最多元素数（即最长合法 V 形子序列的长度）。

基础情况： $f(\text{叶子}) = 1$ ， $f(\text{空}) = 0$ 。
每一步我们保留当前根（+1），然后在左右子树中选更优的一侧递归下去。
$f(\text{root})$ 就是笛卡尔树的高度（从根到叶的最长路径上的节点数）。

第四步：答案

\boxed{\text{答案} = n - h}

其中 $h$ 是大根笛卡尔树的高度。

验证样例

以 [4, 5, 3, 6, 2, 1] 为例，笛卡尔树如上图所示：

$f(4) = 1$ ， $f(3) = 1$ ， $f(1) = 1$
$f(5) = 1 + \max(1, 1) = 2$
$f(2) = 1 + \max(0, 1) = 2$
$f(6) = 1 + \max(2, 2) = 3$
答案 $= 6 - 3 = 3$ 。对应最优方案保留 [6, 2, 1]（ $6 > 2 > 1$ ，纯递减，合法 V 形）。

为什么可以拼接？

你可能会问：把根 $v$ 接到子树的 V 形子序列前面/后面，结果还是 V 形吗？
是的。因为 $v$ 是子树中的最大值，一定大于子序列的所有元素：

$v$ 放左端： $v$ 接上右子树的 V 形 $[d_1, \ldots, d_k, u_1, \ldots, u_m]$ ，得到 $v > d_1 > \cdots > d_k < u_1 < \cdots < u_m$ ，仍是 V 形。
$v$ 放右端：对称，左子树的 V 形后面接 $v$ ，增长的部分末尾加上了更大的 $v$ ，仍是 V 形。

总结

概念	对应关系
笛卡尔树的根	区间最大值，必须放在最终数组端点
选左/右子树	决定保留最大值的哪一侧
笛卡尔树高度 $h$	最多能保留的元素数
答案 $n - h$	最少删除次数
笛卡尔树精确刻画了"每一级的最大值都必须在端点"这一层层递归的约束，这就是它与本题的本质联系。

我们最终采用的呢，是递归式求解做法啊，也就是分治做法，配合使用的那个ST表。

这个是利用了最大值一定不会被删除的这个特性，而且还利用了一个特性，就是只要这个最大值它不在L或者不在R，一定要把L旁边的或者R旁边的全部给删掉。

auto solve=[&](auto && self,ll l,ll r) -> ll {
    if (l>=r) {
        return 0;
    }
    ll mx_i=st.query(l,r);
    ll tmp1=self(self,l,mx_i-1);
    ll tmp2=self(self,mx_i+1,r);
    ll res=min(tmp1 + r-mx_i ,tmp2 + mx_i-l);
    return res;
};

AC代码

AC
https://codeforces.com/contest/2205/submission/365029208

源代码

/**
 * Problem: D. Simons and Beating Peaks
 * Contest: Codeforces Round 1083 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2205/problem/D
 * Created: 2026-03-02 00:06:04
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */

/*
 *2025/12/10 AC https://codeforces.com/contest/2175/submission/352780861
 *2025/3/2 实现了这个 op 函数的传入（可以传入一个 lambda 函数）
 *AC https://codeforces.com/contest/2205/submission/365029208
 *
 */
template<class T,class F>
struct ST {
    ll N;
    vector<vector<T>> dp;
    F op;
    // static T op(const T &a,const T &b) {
    //     return max(a,b);
    // }
    ST(ll N,const vector<T> &a,F fun):N(N),dp(__lg(N)+1,vector<T>(N+5)),op(fun) {
        for (int i=1;i<=N;++i) {
            dp[0][i]=a[i];
        }
        for(int lay=1;lay<=__lg(N);++lay) {
            for(int i=1;i<=N-(1<<(lay-1));++i) {
                dp[lay][i]=op(dp[lay-1][i] , dp[lay-1][i+(1<<(lay-1))]);
            }
        }
    }
    T query(ll l,ll r) {
        ll lay=__lg(r-l+1);
        return op(dp[lay][l],dp[lay][r-(1<<lay)+1]);
    }
};


void Solve() {
    ll N;
    cin >> N;
    vector<ll> A(N+2);
    for (int i=1;i<=N;++i) {
        cin>>A[i];
    }
    auto max_i=[&](const ll &ai,const ll &bi) -> ll{
        if (A[ai]>=A[bi]) {
            return ai;
        }
        return bi;
    };
    vector<ll> vec_idx(N+2);
    for (int i=1;i<=N;++i) {
        vec_idx[i]=i;
    }
    ST<ll,decltype(max_i)> st(N,vec_idx,max_i);
    // 这个其实就是借用了这个最大值要么就必须靠在左边，要么靠在右边
    // 因为最大值实际上是不能删的
    auto solve=[&](auto && self,ll l,ll r) -> ll {
        if (l>=r) {
            return 0;
        }
        ll mx_i=st.query(l,r);
        ll tmp1=self(self,l,mx_i-1);
        ll tmp2=self(self,mx_i+1,r);
        ll res=min(tmp1 + r-mx_i ,tmp2 + mx_i-l);
        return res;
    };
    ll ans=solve(solve,1,N);
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2205/submission/365029208


1
7
6 5 1 7 4 2 3


*/

心路历程（WA，TLE，MLE……）

C++ 14下，因为必须传入模板参数，嗯，可以这样子写其模板类型。

1	ST<ll,decltype(max_i)> st(N,vec_idx,max_i);

嗯，我们可以看到，嗯，这里应该是减L，不应该是减1。

auto solve=[&](auto && self,ll l,ll r) -> ll {
    if (l>=r) {
        return 0;
    }
    ll mx_i=st.query(l,r);
    ll tmp1=self(self,l,mx_i-1);
    ll tmp2=self(self,mx_i+1,r);
    ll res=min(tmp1 + r-mx_i ,tmp2 + mx_i-l);
    return res;
};

Codeforces Round 1083 (Div. 2)——CF-2205-B. Simons and Cakes for Success（如何求一个数全部素因子的乘积？）

Posted on 2026-02-28 Edited on 2026-03-02

题目大意

题目描述
给定一个整数 $n$ ，要求找到最小的正整数 $k$ ，使得 $n$ 能够整除 $k^n$ （即 $n$ 是 $k^n$ 的因数）。
数据保证在给定范围内始终存在答案。

输入格式
第一行包含一个整数 $t$ （ $1 \le t \le 100$ ），表示测试用例的数量。
接下来的 $t$ 行，每行包含一个整数 $n$ （ $2 \le n \le 10^9$ ），表示题目给定的数值。

输出格式
对于每个测试用例，输出一行一个整数，表示满足条件的最小正整数 $k$ 。

样例输入

样例输出

样例解释
在第一个测试用例中（ $n = 8$ ）：
当 $k = 1$ 时， $1^8 = 1$ ， $8$ 不是 $1$ 的因数；
当 $k = 2$ 时， $2^8 = 256$ ， $8$ 是 $256$ 的因数（因为 $256 = 8 \times 32$ ）。
因此，最小可能的 $k$ 为 $2$ 。

在第二个测试用例中（ $n = 12$ ）：
最小的 $k$ 为 $6$ ，因为 $12$ 是 $6^{12} = 2176782336$ 的因数（因为 $2176782336 = 12 \times 181398528$ ）。

思路讲解

不难发现，答案就是 N 的所有素因子的乘积。

不过对于我来说，一个难点是怎么样求，就是N的所有素因子的乘积是多少。（在这道题目的数据范围限制下）

我们这里就用到了一个小trick，就是一个数啊，大于根号N的素因子，有的话只有一个。因此我们就不断的把小的素因子全部都给除掉，那么剩下的一个素因子就是最大的了。（而且这个大于根号N的素因子显然不可能被乘很多遍）

ll opN=N;
for (auto p1:primes) {
    if (p1*p1>N) {
        break;
    }
    if (opN%p1==0) {
        res*=p1;
        while (opN%p1==0) {
            opN/=p1;
        }
    }
}
res*=opN;
cout<<res<<"\n";

AC代码

https://codeforces.com/contest/2205/submission/364837938

源代码

/**
 * Problem: B. Simons and Cakes for Success
 * Contest: Codeforces Round 1083 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2205/problem/B
 * Created: 2026-02-28 20:08:34
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */
//  minp[i] 存储的是i的最小素因数
// https://www.luogu.com.cn/record/221554377
vector<ll> minp,primes;
void sieve(ll n){
    minp.assign(n+5,0);
    // minp[1]=1;  // 加了这句话可能把 1 误判成素数，要小心
    for(int i=2;i<=n;++i){
        if(minp[i]==0){		// 是素数
            minp[i]=i;
            primes.push_back(i);
        }
        for(auto p:primes){
            if(i*p>n){	// 超范围了
                break;
            }
            minp[i*p]=p;
            // 为了保证每个合数都只被其【最小的】那个质因数标记一次 break
            // i * p_next = (p * k) * p_next 最小的应该是p
            if(p==minp[i]){
                break;
            }
        }
    }
}

void Solve() {
    ll N;
    cin >> N;
    ll res=1;
    ll opN=N;
    for (auto p1:primes) {
        if (p1*p1>N) {
            break;
        }
        if (opN%p1==0) {
            res*=p1;
            while (opN%p1==0) {
                opN/=p1;
            }
        }
    }
    res*=opN;
    cout<<res<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    sieve(1e6);
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2205/submission/364837938

*/

心路历程（WA，TLE，MLE……）

Educational Codeforces Round 187 (Rated for Div. 2)-CF-Edu-187-D. Divisibility Game（较大数据量下 vector 套 vector 的调和级数因数分解会出问题）（觉得有点把握不住，就上 int128，一般就比较难卡掉了）（在高版本 C++，要自己定义 lcm 函数就写 lcm128 什么的，就写 lcm 可能给你直接调 std::lcm）

Posted on 2026-02-26

题目大意

题目大意

Alice 和 Bob 在玩一个游戏。给定两个数组：包含 $n$ 个元素的数组 $a$ 和包含 $m$ 个元素的数组 $b$ 。

两人轮流进行操作，Alice 先手。在每个回合中，玩家需要从数组 $a$ 中选择一个数字 $x$ ，并从数组 $b$ 中选择一个数字 $y$ 。

Alice 的规则：选择的 $y$ 必须能被 $x$ 整除。
Bob 的规则：选择的 $y$ 必须不能被 $x$ 整除。

选定 $x$ 和 $y$ 后， $y$ 会从数组 $b$ 中被移除（如果数组中存在多个相同的 $y$ ，只移除其中一个），而 $x$ 仍然保留在数组 $a$ 中。无法进行合法操作（即无法选出满足自身规则的 $x$ 和 $y$ ）的玩家将输掉游戏。

假设双方都采取最优策略，请判断谁会赢得游戏。

输入格式

第一行包含一个整数 $t$ （ $1 \le t \le 10^4$ ），表示测试用例的数量。

对于每个测试用例：
第一行包含两个整数 $n$ 和 $m$ （ $1 \le n, m \le 10^6$ ）。
第二行包含 $n$ 个整数 $a_i$ （ $1 \le a_i \le n+m$ ），表示数组 $a$ 的元素。
第三行包含 $m$ 个整数 $b_i$ （ $1 \le b_i \le n+m$ ），表示数组 $b$ 的元素。

保证所有测试用例中 $n$ 的总和以及 $m$ 的总和均不超过 $10^6$ 。

输出格式

对于每个测试用例，输出获胜者的名字：如果 Alice 赢，输出 Alice；如果 Bob 赢，输出 Bob。

样例输入

3
9 3
3 2 4 2 2 4 4 2 4
6 7 12
10 3
3 2 5 4 2 5 3 4 4 4
10 7 13
1 5
1
1 2 3 4 5

样例输出

1
2
3

Alice
Bob
Alice

样例解释

对于第一个测试用例，Alice 的获胜过程如下：

Alice 的回合：选择 $x=3, y=6$ （ $6$ 能被 $3$ 整除）。操作后 $6$ 从数组 $b$ 中移除，此时 $b=[7, 12]$ 。
Bob 的回合：选择 $x=3, y=7$ （ $7$ 不能被 $3$ 整除）。Bob 在这个回合只能选择 $y=7$ ，因为对于 $y=12$ ，数组 $a$ 中找不到任何不能整除它的 $x$ 。操作后 $7$ 从数组 $b$ 中移除，此时 $b=[12]$ 。
Alice 的回合：选择 $x=4, y=12$ （ $12$ 能被 $4$ 整除）。操作后 $12$ 从数组 $b$ 中移除，此时数组 $b$ 变为空。
Bob 的回合：数组 $b$ 已经为空，Bob 无法进行任何操作，因此 Bob 输掉游戏，Alice 获胜。

思路讲解

OK，我们说回来。这个D为什么交了5发还是没过呢？主要是因为就是这个D，它的数据量比较大。使用Victor victor或者victor的这种调和级数写法呢，它这个时间会超。可以使用vis 数组标记所有 a 的倍数。这样子可以避免卡常。

ll cnt_un_divide=0,cnt_all_divide=0;
vector<char> vis(N+M+2);
for (auto a:A) {
    for (ll i=1;i<=N+M;++i) {
        if (i*a>N+M) {
            break;
        }
        vis[i*a]=true;
    }
}

然后为什么标题里面提了不要用 while 循环？是因为涉及累加的逻辑（在 D 的对拍暴力程序当中），直接 continue 以后，while 循环的这个累加就崩掉了。

AC代码

AC
https://codeforces.com/contest/2203/submission/364454955

源代码

/**
 * Problem: D. Divisibility Game
 * Contest: Educational Codeforces Round 187 (Rated for Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2203/problem/D
 * Created: 2026-02-25 22:56:31
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)2e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */

i128 lcm128(i128 a,i128 b) {
    i128 res=a*b/__gcd(a,b);
    return res;
}
// vector<ll> factor[MAXN];
void Solve() {
    ll N,M;
    cin >> N >> M;
    vector<ll> A(N),B(M);
    for (int i=0;i<N;++i) {
        cin>>A[i];
    }
    for (int i=0;i<M;++i) {
        cin>>B[i];
    }
    // vector<vector<ll>> factor(N+M+2);
    // factor.reserve(N+M+2);
    // for (int i=1;i<=N+M;++i) {
    //     for (int j=1;j<=N+M;++j) {
    //         if (i*j>N+M) {
    //             break;
    //         }
    //         factor[i*j].push_back(i);
    //     }
    // }
    sort(all(A));
    A.resize(unique(all(A))-A.begin());
    __int128 acc_lcm=A[0];
    for (int i=1;i<A.size();++i) {
        acc_lcm=lcm128(acc_lcm,A[i]);
    }
    ll cnt_un_divide=0,cnt_all_divide=0;
    vector<char> vis(N+M+2);
    for (auto a:A) {
        for (ll i=1;i<=N+M;++i) {
            if (i*a>N+M) {
                break;
            }
            vis[i*a]=true;
        }
    }
    for (int i=0;i<M;++i) {
        if (!vis[B[i]]) {
            cnt_un_divide++;
        }
    }

    for (int i=0;i<M;++i) {
        if (B[i]%acc_lcm==0) {
            cnt_all_divide++;
        }
    }

    ll rem=M-cnt_all_divide-cnt_un_divide;
    for (int idx=1;;++idx) {
        if (idx&1) {
            if (rem>0) {
                rem--;
                continue;
            }
            if (cnt_all_divide>0) {
                cnt_all_divide--;
                continue;
            }
            cout<<"Bob\n";
            return;
        }else {
            if (rem>0) {
                rem--;
                continue;
            }
            if (cnt_un_divide>0) {
                cnt_un_divide--;
                continue;
            }
            cout<<"Alice\n";
            return;
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif
    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2203/submission/364454955

1
9 3
3 2 4 2 2 4 4 2 4
6 7 12

1
1 5
1
1 2 3 4 5

*/

心路历程（WA，TLE，MLE……）

后面还被系统测试阴了一手，把这个LCM改成128，用INT128就可以了，这个叫什么，当时其实我就知道这里应该是会有点问题的，想用这个128嘛，但是可能还是犹豫还是犹豫了。

i128 lcm128(i128 a,i128 b) {
    i128 res=a*b/__gcd(a,b);
    return res;
}

题目大意

思路讲解

AC代码

心路历程（WA，TLE，MLE……）

你的疑惑

其实不矛盾，因为两个前缀是不同长度的对象

用样例 1 具体看

逻辑链条

好的，我用前三个样例来逐步模拟。

样例 1：T=[1,1,2,1]T = [1, 1, 2, 1]T=[1,1,2,1]，答案 =4= 4=4

样例 2：T=[1,2,3,1]T = [1, 2, 3, 1]T=[1,2,3,1]，答案 =7= 7=7

样例 3：T=[1,3,2,3,3,2]T = [1, 3, 2, 3, 3, 2]T=[1,3,2,3,3,2]，答案 =22= 22=22

好的，我用样例 1（T=[1,1,2,1]T = [1, 1, 2, 1]T=[1,1,2,1]）来把这件事彻底讲清楚。

一、什么是"本原"

二、非本原段为什么不贡献——用具体例子看"冗余"

例子 A：T[2..4]=[1,2,1]T[2..4] = [1, 2, 1]T[2..4]=[1,2,1]，周期 2，非本原

例子 B：T[1..4]=[1,1,2,1]T[1..4] = [1, 1, 2, 1]T[1..4]=[1,1,2,1]，周期 3，非本原

三、本原段为什么能贡献——它的结果是"全新的"

例子 C：T[3..4]=[2,1]T[3..4] = [2, 1]T[3..4]=[2,1]，本原

四、总结原理

核心：交换两块

字符串交换的经典定理

用具体例子感受

等价的周期条件

实际计算方法

第一步：以 i=0i = 0i=0 为左端点进行拓展

第二步：以 i=1i = 1i=1 为左端点进行拓展

第三步：以 i=2i = 2i=2 为左端点进行拓展

第四步：以 i=3i = 3i=3 为左端点进行拓展

第五步：以 i=4i = 4i=4 为左端点进行拓展

第六步：以 i=5i = 5i=5 为左端点进行拓展

模拟结论

题目大意

思路讲解

AC代码

心路历程（WA，TLE，MLE……）

题目大意

思路讲解

笛卡尔树

引入

单调栈构建笛卡尔树

过程

笛卡尔树与 Treap

C++ 实现

一、笛卡尔树是什么

构造方式（以大根笛卡尔树为例）

二、为什么这道题和笛卡尔树有关

第一步：理解"cool"数组的结构

第二步：全局最大值 nnn 必定保留且在端点

第三步：递归结构 = 笛卡尔树

第四步：答案

验证样例

为什么可以拼接？

总结

AC代码

心路历程（WA，TLE，MLE……）

题目大意

思路讲解

AC代码

心路历程（WA，TLE，MLE……）

题目大意

思路讲解

AC代码

心路历程（WA，TLE，MLE……）

样例 1： $T = [1, 1, 2, 1]$ ，答案 $= 4$

样例 2： $T = [1, 2, 3, 1]$ ，答案 $= 7$

样例 3： $T = [1, 3, 2, 3, 3, 2]$ ，答案 $= 22$

好的，我用样例 1（ $T = [1, 1, 2, 1]$ ）来把这件事彻底讲清楚。

例子 A： $T[2..4] = [1, 2, 1]$ ，周期 2，非本原

例子 B： $T[1..4] = [1, 1, 2, 1]$ ，周期 3，非本原

例子 C： $T[3..4] = [2, 1]$ ，本原

第一步：以 $i = 0$ 为左端点进行拓展

第二步：以 $i = 1$ 为左端点进行拓展

第三步：以 $i = 2$ 为左端点进行拓展

第四步：以 $i = 3$ 为左端点进行拓展

第五步：以 $i = 4$ 为左端点进行拓展

第六步：以 $i = 5$ 为左端点进行拓展

第二步：全局最大值 $n$ 必定保留且在端点