AT_arc187_e 做题笔记

· · 题解

显然这序列可以直接看作一个环，然后通过手玩可以注意到一些性质：

然后有一些 corner case，就是不能操作就无解，初始排列输出 1，全部相同输出 n!，n=4 的旋转有点特殊也要特殊讨论。以及因为连续段不能消除，所以一个数有两个连续段也无解，下面不讨论这几种情况。

然后就大概可以开始做了。因为你汇聚起来的肯定可以插回去，因此不妨把多的数先全部放在第一段，每次往后面移动插入。这样可以看作这样的一个东西：你初始有一些数，你要在他们之间任意插进去一些数生成出一个排列，并且要满足可以被上面的操作生成，然后这个数列可以任意旋转（不能任意旋转的情况 n 肯定是偶数且旋转是每次挪 2，那答案除 2 即可）。

前面是好做的，考虑一个排序什么时候可以被生成。一个充要的条件是存在一对被新插入的数在环上距离不超过 2。必要性比较显然，通过上面的方式生成，最后一次修改肯定是修改了 3 个连续位置中的两个，那他们肯定距离不超过 2。充分性呢？考虑你是每次把这些多的数往后挪，顺便把一些数留下来并修改，你填最后的这个位置之前显然可以先转一圈把其他位置填完，然后还剩下至少两个数肯定足够转回来的。因此这个条件是充要的。

问题转化为：你初始有一些数互不相同的数，你要在他们之间任意插进去一些数生成出一个排列，然后插进去的数至少有两个的距离不超过 2，数列可以任意旋转。发现这个限制不好做，考虑容斥。

首先是所有情况，首先设原本有 k 连续段，那现在要插入 m=n-k 个数，考虑先把 m 个数确定位置，那剩下的 k 个数就只有旋转的方案了，贡献是 \operatorname{A}_{n}^m\cdot k，然后拆一下可以得到是 \frac{n!}{(k-1)!}。

考虑任意两个插入的数之间都需要至少 2 个间隔的方案数。插板法可以得到方案数为 C_{k-m-1}^{m-1}，然后考虑确定插入数的位置，随便确定一个的位置之后剩下的位置都定下来了，贡献是 n\cdot (m-1)!，最后原本的数可以旋转，贡献是 k，全部相乘得 C_{k-m-1}^{m-1}\cdot n\cdot (m-1)!\cdot k。

最后答案就上面两个相减。

::::success[code]

#include<bits/stdc++.h>
#define ll long long
#define mod 998244353
using namespace std;
int n,a[10000005],ans;
ll jc[10000005],inv[10000005];
ll fpow(ll a,int p){return (p?fpow(a*a%mod,p>>1)*(p&1?a:1)%mod:1);}
bool tong[10000005];
ll C(int n,int m){if(n<0||m<0||n<m)return 0;return jc[n]*inv[m]%mod*inv[n-m]%mod;}
int main(){
    ios::sync_with_stdio(0);
//  freopen("fx.in","r",stdin);
//  freopen("fx.out","w",stdout);
    cin>>n;
    jc[0]=1;
    for(int i=1;i<=n;i++)cin>>a[i],jc[i]=jc[i-1]*i%mod;
    inv[n]=fpow(jc[n],mod-2);
    for(int i=n-1;~i;i--)inv[i]=inv[i+1]*(i+1)%mod;
    vector<pair<int,int> > v;
    v.reserve(n);
    for(int i=1;i<=n;i++){
        if(a[i]!=a[i-1])v.push_back({a[i],1});
        else v.back().second++;
    }
    if(v[0].first==v.back().first&&v.size()>1){
        v[0].second+=v.back().second;
        v.pop_back();
    }
    for(auto i:v){
        if(tong[i.first]){
            cout<<0;
            return 0;
        }
        tong[i.first]=1;
    }
    if(v.size()==1){
        ll ans=1;
        for(int i=1;i<=n;i++)ans=ans*i%mod;
        cout<<ans;
        return 0;
    }
    if(v.size()!=n){
        bool bad=1;
        for(auto i:v)if(i.second>2)bad=0;
        if(bad){
            cout<<0;
            return 0;
        }
    }else{
        cout<<1;
        return 0;
    }
    if(v.size()==n-2){
        if(n!=4)cout<<n*(ll)(n-2)*4/(n&1?1:2)%mod;
        else cout<<24<<'\n';
        return 0;
    }
    int k=v.size(),m=n-k;
//  ll ans=C(n,m)*jc[m]%mod*k;
//  cerr<<jc[n]*inv[k-1]%mod<<'\n';
    ll ans=jc[n]*inv[k-1]%mod-n*C(k-m-1,m-1)%mod*jc[m-1]%mod*k%mod+mod;ans%=mod;
    cout<<ans*((n&1)||m!=2?1:(mod+1)/2)%mod;
}

::::

附一下我看的鱼教版题解，我觉得讲的还挺细的。看不懂我写的可以看着补充一下，参考的是题解区原本 Acoipp 的题解。

::::info[from deepseek]

下面我按“为什么”的顺序把这份题解和 std 逐段对上讲清楚。先说明：这个环境里没有 g++，所以我把 std 逐句翻译成了 Python，并对工作区里的小样例（fx1–fx6，也就是题面 1/2/3 以及 1 2 3、4 4 4 4、1 2 3 3 3 4）手算了 std 的走向，结果与 .ans 全部一致；下面的推导也都是围绕这个 std 展开的。

0. 先厘清"操作"到底做了什么

一次操作：取三个连续且相等的位置 i,i+1,i+2，把其中两个位置改成 1\sim N 的任意整数。

关键观察（后面所有结论的来源）：

  1. 没有删除，只有"改值"。操作只改变某些位置的值，位置本身不消失、不移动。
  2. 所以一个值 v 的"副本们"彼此之间的环形相对顺序永远不会改变；如果你不修改某个副本，它就一直在那里。
  3. 一个值 v 的副本，如果中间夹着别的值（即在 A 中 v 的副本不是连续的一段），那么夹在中间的那些值永远不会消失（因为没有"删除"操作，只有把某个位置改成别的值，而那些中间的位置本身也需要三连才能被改）。结论：最终 P 是排列，每个值只出现一次；若 v 在 A 中不连续，P 里只允许一个 v，但"顺序保留"要求 v 的两个副本分别在夹层两侧，矛盾 ⇒ 答案 0。

这就是 std 里

if(ls[i] && rs[i]-ls[i]+1 != cnt[i]) return cout<<0<<endl,0;

的含义：[\text{ls}_i,\text{rs}_i] 区间长度必须等于 cnt_i，即该值的所有出现位置连成一段。

配套地，程序先把环转一下（找第一个 a_i\ne a_{i+1} 的位置 i，整体左移 i），使得 A_1\ne A_N，于是"连续段"（块）的定义是唯一、无歧义的。答案与旋转无关，因为操作是在环上定义的。

1. 三种"显然"情况

情况 判据（std 中的写法） 答案
A 本身是排列 所有 cnt_i=1（alls 变量） 1
所有元素相同 循环找 a_i\ne a_{i+1}，找不到（i==n+1） n!
永远无法操作 有任何块不连续 0
没有长度 \ge 3 的块 cnt[i]>=3 从未出现（i>n） 0

最后一条要注意：经过"连续性检查"后还没返回，说明存在某个 cnt\ge 2；如果所有 cnt\le 2，就永远不会出现三连，于是永远无法操作，答案 0。程序里用 if(cnt[i]>=3) break; 然后 if(i>n) return 0; 实现。

2. 把状态压缩成"块"

经过上面的检查，A 是若干个块拼起来的：每个块内值相同，块与块的值互不相同。设块数 k（cntt），第 i 块长度 s_i，\sum s_i=n。

因为最终 P 是排列：

于是问题变成：在"旧值环序固定"的前提下，把 m 个新数插进去，哪些 P 可达。

3. 分支一：k=n-2（cntt == n-2），即只有两个新数

此时 \sum s_i = n = k+2，多出的 2 个元素只能集中在某一块里：

所以只剩"一个长度 3 的块，其余全为 1"的情形。设这个块是 v,v,v 占位置 p,p+1,p+2。

std 里的对应代码：

if(cntt==n-2){
    if(n==4){ cout<<24<<endl; return 0; }
    ll ans = 4*(n-2)*n%mod;
    if(n!=4 && n%2==0) ans = ans*qmi(2,mod-2,mod)%mod;
    cout<<ans<<endl; return 0;
}

注意这里的 qmi(2,mod-2,mod) 就是模意义下除以 2。也验证了 fx6（1 2 3 3 3 4，n=6）：4\cdot4\cdot6/2=48。

4. 分支二：k\le n-3（m\ge 3）—— 本题的核心

4.1 可达性的判据

在"旧值环序固定"的前提下，P 可达 \iff 存在两个新数，它们在 P 中的环距离 \le 2。

于是

\text{答案} = \#\{\text{旧值环序保留的 }P\} - \#\{\text{在此基础上所有新数两两环距离}\ge 3\text{ 的 }P\}.

4.2 总数：n!/(k-1)!

- 在环上选 $k$ 个位置放旧值：$\binom{n}{k}$； - 这 $k$ 个位置的环序固定，但可以任选"起点"（$v_1$ 落在哪个位置），共 $k$ 种； - 剩下的 $m$ 个位置由新值任意填：$m!$ 种。 $$ \binom{n}{k}\cdot k\cdot m! = \frac{n!}{k!\,m!}\cdot k\cdot m! = \frac{n!}{(k-1)!}. $$ std 里写的是 ```cpp jc[n-1]*inv[cntt-1] // = (n-1)!/(k-1)! ... cout << ( ... - ans + mod) * n % mod; // 再乘 n，得到 n!/(k-1)! ``` 即 `(jc[n-1]*inv[cntt-1])*n = n!/(k-1)!`。 ### 4.3 "坏"的个数：容斥 + 隔板法 坏 $P$ = 旧值环序保留，且**任意两个新数环距离 $\ge 3$**。 "环距离 $\ge 3$" 等价于：任意两个相邻新数之间至少隔着 **2 个旧值**（因为它们之间只能放旧值，且旧值不可重复）。 把 $k$ 个旧值按环序分配到 $m$ 个"间隔"里（间隔就是新数之间的空档），每个间隔 $\ge 2$ 个旧值。这就是题解里的 $$ f(n,m)=\binom{n-m-1}{m-1}\quad(\text{把 } n \text{ 个球放入 } m \text{ 个盒子，每个盒子 }\ge 2). $$ std 把它写成 ```cpp inline ll solve(ll x,ll y){ // 把 x 个球放入 y+1 个盒子，每盒 >=2 x -= (y+1); return C(x-1,y); // = C(x-y-2, y) = f(x, y+1) } ``` 调用时 `y = n-cntt-1 = m-1`，也就是"$m$ 个盒子"。 为了避免"环上整体旋转"造成重复计数，枚举**第一个新数**的落点：它落在第 $i$ 个旧块之后（$i=1..k$）。此时能参与分配的旧值个数为 `ball`： $$ \text{ball} = \begin{cases} k, & i=1,\\ k-i+2, & i\ge 2.\end{cases} $$ （std 里 `ball=cntt-i+1; if(i>1) ball++;` 正是这个。）对应的坏方案数贡献为 $$ m!\cdot f(\text{ball},\,m) = m!\cdot\binom{\text{ball}-m-1}{m-1}, $$ 累加得到 $B$。`ball` 太小时组合数为 0（$C$ 函数对非法下标返回 0），这也解释了样例 1、样例 3 里 $B=0$。 std 里： ```cpp ll ans = 0; for(i=1;i<=cntt;i++){ ll ball = cntt-i+1; if(i==1) ball+=0; else ball+=1; ans = (ans + jc[n-cntt]*solve(ball, n-cntt-1)) % mod; } ``` `jc[n-cntt] = m!`，`solve(ball, m-1)` 就是上面的 $f(\text{ball},m)$。 ### 4.4 合并 $$ \text{answer}=\left(\frac{n!}{(k-1)!}-B\right)\bmod 998244353 =\big(\texttt{jc[n-1]*inv[cntt-1]}-B\big)\cdot n \bmod p . $$ --- ## 5. 用 std 走一遍样例，确认理解 **样例 1**：`1 2 3 3 1 1`，$n=6$。 - $a_1\ne a_2$，旋转后为 `2 3 3 1 1 1`；块：`[2] [3,3] [1,1,1]`，连续性检查通过，$k=3$。 - $k=3\ne n-2=4$，进入核心分支，$m=3$。 - $\text{ball}$：$i=1\to3$，$i=2\to3$，$i=3\to2$；`solve(3,2)=C(-1,2)=0`，`solve(2,2)=C(-2,2)=0`，故 $B=0$。 - 答案 $=\frac{6!}{2!}=360$。✓ **样例 2**：`3 1 3 4 1`，值 1 出现在位置 2、5，中间夹着 3、4 ⇒ 不连续 ⇒ 0。✓ **样例 3**：`1 1 1 8 8 8 7 7 7 10`，旋转后块长 $3,3,3,1$，$k=4$，$m=6$，$\text{ball}\le 4<2m$ ⇒ $B=0$，答案 $\frac{10!}{3!}=604800$。✓ **fx6**：`1 2 3 3 3 4`，块长 $1,1,3,1$，$k=4=n-2$，$n=6$ 偶数 ⇒ $4\cdot4\cdot6/2=48$。✓ **fx4**：`1 2 3` 是排列 ⇒ 1；**fx5**：全相等 ⇒ $4!=24$。✓ --- ## 6. 容易踩的坑（也是题解里表述含糊的地方） 1. 题解说"没有在 $A$ 中间的两个数字"，其实是"**没有在 $A$ 中出现的**两个数字"（即两个新数）——笔误。 2. "相对位置保留"要理解成：**旧值的副本按 $A$ 中的环形顺序排列，且同一个旧值的副本仍连成一段**。因为最终是排列，每个旧值只剩一个副本，所以只需保证 $k$ 个旧值的环序。 3. 被替换的两个数**可以相等，也可以是已经出现过的数**（题目只说"替换成 $1\sim N$ 的整数"）。这正是 std 里 $C$ 的下标可能为负、返回 0 的原因：把"球数不够"（即间隔无法都塞满 2 个旧值）的情形自然排除。 4. $n=4$ 必须特判：平移 1 位可达，导致"除以 2"不成立，直接 $24$。 5. 复杂度：预处理阶乘/逆元、一次线性扫描，$O(n)$ 时间、$O(n)$ 空间。 --- ## 7. 一句话总结各分支 设 $k$ 为块数（不同值的个数）： - 有值不连续 → $0$；全是 1 次 → $1$；全相同 → $n!$；最大块长 $\le 2$ → $0$； - $k=n-2$：$n=4$ 时为 $24$，否则 $4(n-2)n$（$n>4$ 偶数再除 2）； - $k\le n-3$：$\dfrac{n!}{(k-1)!}-\sum_{i=1}^{k} m!\,f(\text{ball}_i,m)$，其中 $m=n-k$，$\text{ball}_i=k-i+2\ (i\ge2)$、$\text{ball}_1=k$，$f(x,m)=\binom{x-m-1}{m-1}$。 这就是 std 的完整逻辑；三组样例和 fx4–fx6 都对得上。下面我按“为什么”的顺序把这份题解和 std 逐段对上讲清楚。先说明：这个环境里没有 `g++`，所以我把 std 逐句翻译成了 Python，并对工作区里的小样例（fx1–fx6，也就是题面 1/2/3 以及 `1 2 3`、`4 4 4 4`、`1 2 3 3 3 4`）手算了 std 的走向，结果与 `.ans` 全部一致；下面的推导也都是围绕这个 std 展开的。 --- ## 0. 先厘清"操作"到底做了什么 一次操作：取三个连续且相等的位置 $i,i+1,i+2$，把其中**两个**位置改成 $1\sim N$ 的任意整数。 关键观察（后面所有结论的来源）： 1. **没有删除，只有"改值"**。操作只改变某些位置的值，位置本身不消失、不移动。 2. 所以一个值 $v$ 的"副本们"彼此之间的**环形相对顺序**永远不会改变；如果你不修改某个副本，它就一直在那里。 3. 一个值 $v$ 的副本，如果中间夹着别的值（即在 $A$ 中 $v$ 的副本不是连续的一段），那么夹在中间的那些值永远不会消失（因为没有"删除"操作，只有把某个位置改成别的值，而那些中间的位置本身也需要三连才能被改）。**结论：最终 $P$ 是排列，每个值只出现一次；若 $v$ 在 $A$ 中不连续，$P$ 里只允许一个 $v$，但"顺序保留"要求 $v$ 的两个副本分别在夹层两侧，矛盾 ⇒ 答案 0。** 这就是 std 里 ```cpp if(ls[i] && rs[i]-ls[i]+1 != cnt[i]) return cout<<0<<endl,0; ``` 的含义：$[\text{ls}_i,\text{rs}_i]$ 区间长度必须等于 $cnt_i$，即该值的所有出现位置连成一段。 配套地，程序先把环转一下（找第一个 $a_i\ne a_{i+1}$ 的位置 $i$，整体左移 $i$），使得 $A_1\ne A_N$，于是"连续段"（块）的定义是唯一、无歧义的。答案与旋转无关，因为操作是在环上定义的。 --- ## 1. 三种"显然"情况 | 情况 | 判据（std 中的写法） | 答案 | |---|---|---| | $A$ 本身是排列 | 所有 $cnt_i=1$（`alls` 变量） | $1$ | | 所有元素相同 | 循环找 $a_i\ne a_{i+1}$，找不到（`i==n+1`） | $n!$ | | 永远无法操作 | 有任何块不连续 | $0$ | | 没有长度 $\ge 3$ 的块 | `cnt[i]>=3` 从未出现（`i>n`） | $0$ | 最后一条要注意：经过"连续性检查"后还没返回，说明存在某个 $cnt\ge 2$；如果所有 $cnt\le 2$，就永远不会出现三连，于是永远无法操作，答案 0。程序里用 `if(cnt[i]>=3) break;` 然后 `if(i>n) return 0;` 实现。 --- ## 2. 把状态压缩成"块" 经过上面的检查，$A$ 是若干个块拼起来的：每个块内值相同，块与块的值互不相同。设块数 $k$（`cntt`），第 $i$ 块长度 $s_i$，$\sum s_i=n$。 因为最终 $P$ 是排列： - 每个旧值最终**只剩 1 个副本**（其余都被改掉）； - 新值（$A$ 中没出现过的数）恰好 $m=n-k$ 个，每个出现一次； - 旧值在 $P$ 中仍是"一段"（副本顺序不能乱，也不能被别的旧值插入），且 $k$ 个旧值在 $P$ 中的**环形顺序与 $A$ 中相同**。 于是问题变成：在"旧值环序固定"的前提下，把 $m$ 个新数插进去，哪些 $P$ 可达。 --- ## 3. 分支一：$k=n-2$（`cntt == n-2`），即只有两个新数 此时 $\sum s_i = n = k+2$，多出的 2 个元素只能集中在某一块里： - 若分布是 $3+1+\cdots+1$：恰有一个长度 3 的块，可以操作； - 若是 $2+2+1+\cdots$：所有块长度 $\le 2$，上一节已判 0。 所以只剩"一个长度 3 的块，其余全为 1"的情形。设这个块是 $v,v,v$ 占位置 $p,p+1,p+2$。 - 只能对它操作：三个位置里留一个 $v$，另外两个变成两个新数 $x,y$（顺序 2 种，留下的是哪一个 3 种）。 - 所以 $x,y$ 在 $P$ 中的**环距离必然 $\le 2$**（它们来自三个连续位置中的两个）——这是这一步的充要条件。 - 于是计数只要枚举 $x,y$ 放在哪里： - $x$ 有 $n$ 个位置；$y$ 要在它左右各 2 个位置里选（距离 $\le 2$），共 4 种；再乘"块的位置"带来的 $n-2$ 种，得到 $4(n-2)n$。 - **偶数 $n>4$ 要除以 2**：题解里那段"整体平移 2 位"的意思是，$n$ 为偶数时，每次完整操作都会把图案整体平移 2 位，$P$ 与"$P$ 右移 2 位"是同一个 $2$-周期结构被数了两次（$n$ 奇数没有这个对称性）；$n=4$ 例外，因为 $1,1,1,3\to 3,1,1,1$ 只平移 1 位，所以 $n=4$ 直接是 $4!=24$。 std 里的对应代码： ```cpp if(cntt==n-2){ if(n==4){ cout<<24<<endl; return 0; } ll ans = 4*(n-2)*n%mod; if(n!=4 && n%2==0) ans = ans*qmi(2,mod-2,mod)%mod; cout<<ans<<endl; return 0; } ``` 注意这里的 `qmi(2,mod-2,mod)` 就是模意义下除以 2。也验证了 fx6（`1 2 3 3 3 4`，$n=6$）：$4\cdot4\cdot6/2=48$。 --- ## 4. 分支二：$k\le n-3$（$m\ge 3$）—— 本题的核心 ### 4.1 可达性的判据 > 在"旧值环序固定"的前提下，$P$ 可达 $\iff$ 存在两个新数，它们在 $P$ 中的环距离 $\le 2$。 - **必要性**：看生成 $P$ 的**最后一步**。最后一步作用在三个连续相等的位置上，把其中两个改成新数 $u,v$。它们位于三个连续位置中的两个，环距离 $\le 2$；之后不再操作，所以 $P$ 中 $u,v$ 的距离仍 $\le 2$。 - **充分性**：若某对位置相距 $\le 2$ 能放新数，其余新数可以按任意顺序"逐步"生成（每次操作生成两个新数时，旧值环序自动保持），最后用那对相距 $\le 2$ 的位置收尾即可。 于是 $$ \text{答案} = \#\{\text{旧值环序保留的 }P\} - \#\{\text{在此基础上所有新数两两环距离}\ge 3\text{ 的 }P\}. $$ ### 4.2 总数：$n!/(k-1)! - 在环上选 $k$ 个位置放旧值：$\binom{n}{k}$； - 这 $k$ 个位置的环序固定，但可以任选"起点"（$v_1$ 落在哪个位置），共 $k$ 种； - 剩下的 $m$ 个位置由新值任意填：$m!$ 种。 $$ \binom{n}{k}\cdot k\cdot m! = \frac{n!}{k!\,m!}\cdot k\cdot m! = \frac{n!}{(k-1)!}. $$ std 里写的是 ```cpp jc[n-1]*inv[cntt-1] // = (n-1)!/(k-1)! ... cout << ( ... - ans + mod) * n % mod; // 再乘 n，得到 n!/(k-1)! ``` 即 `(jc[n-1]*inv[cntt-1])*n = n!/(k-1)!`。 ### 4.3 "坏"的个数：容斥 + 隔板法 坏 $P$ = 旧值环序保留，且**任意两个新数环距离 $\ge 3$**。 "环距离 $\ge 3$" 等价于：任意两个相邻新数之间至少隔着 **2 个旧值**（因为它们之间只能放旧值，且旧值不可重复）。 把 $k$ 个旧值按环序分配到 $m$ 个"间隔"里（间隔就是新数之间的空档），每个间隔 $\ge 2$ 个旧值。这就是题解里的 $$ f(n,m)=\binom{n-m-1}{m-1}\quad(\text{把 } n \text{ 个球放入 } m \text{ 个盒子，每个盒子 }\ge 2). $$ std 把它写成 ```cpp inline ll solve(ll x,ll y){ // 把 x 个球放入 y+1 个盒子，每盒 >=2 x -= (y+1); return C(x-1,y); // = C(x-y-2, y) = f(x, y+1) } ``` 调用时 `y = n-cntt-1 = m-1`，也就是"$m$ 个盒子"。 为了避免"环上整体旋转"造成重复计数，枚举**第一个新数**的落点：它落在第 $i$ 个旧块之后（$i=1..k$）。此时能参与分配的旧值个数为 `ball`： $$ \text{ball} = \begin{cases} k, & i=1,\\ k-i+2, & i\ge 2.\end{cases} $$ （std 里 `ball=cntt-i+1; if(i>1) ball++;` 正是这个。）对应的坏方案数贡献为 $$ m!\cdot f(\text{ball},\,m) = m!\cdot\binom{\text{ball}-m-1}{m-1}, $$ 累加得到 $B$。`ball` 太小时组合数为 0（$C$ 函数对非法下标返回 0），这也解释了样例 1、样例 3 里 $B=0$。 std 里： ```cpp ll ans = 0; for(i=1;i<=cntt;i++){ ll ball = cntt-i+1; if(i==1) ball+=0; else ball+=1; ans = (ans + jc[n-cntt]*solve(ball, n-cntt-1)) % mod; } ``` `jc[n-cntt] = m!`，`solve(ball, m-1)` 就是上面的 $f(\text{ball},m)$。 ### 4.4 合并 $$ \text{answer}=\left(\frac{n!}{(k-1)!}-B\right)\bmod 998244353 =\big(\texttt{jc[n-1]*inv[cntt-1]}-B\big)\cdot n \bmod p . $$ --- ## 5. 用 std 走一遍样例，确认理解 **样例 1**：`1 2 3 3 1 1`，$n=6$。 - $a_1\ne a_2$，旋转后为 `2 3 3 1 1 1`；块：`[2] [3,3] [1,1,1]`，连续性检查通过，$k=3$。 - $k=3\ne n-2=4$，进入核心分支，$m=3$。 - $\text{ball}$：$i=1\to3$，$i=2\to3$，$i=3\to2$；`solve(3,2)=C(-1,2)=0`，`solve(2,2)=C(-2,2)=0`，故 $B=0$。 - 答案 $=\frac{6!}{2!}=360$。✓ **样例 2**：`3 1 3 4 1`，值 1 出现在位置 2、5，中间夹着 3、4 ⇒ 不连续 ⇒ 0。✓ **样例 3**：`1 1 1 8 8 8 7 7 7 10`，旋转后块长 $3,3,3,1$，$k=4$，$m=6$，$\text{ball}\le 4<2m$ ⇒ $B=0$，答案 $\frac{10!}{3!}=604800$。✓ **fx6**：`1 2 3 3 3 4`，块长 $1,1,3,1$，$k=4=n-2$，$n=6$ 偶数 ⇒ $4\cdot4\cdot6/2=48$。✓ **fx4**：`1 2 3` 是排列 ⇒ 1；**fx5**：全相等 ⇒ $4!=24$。✓ --- ## 6. 容易踩的坑（也是题解里表述含糊的地方） 1. 题解说"没有在 $A$ 中间的两个数字"，其实是"**没有在 $A$ 中出现的**两个数字"（即两个新数）——笔误。 2. "相对位置保留"要理解成：**旧值的副本按 $A$ 中的环形顺序排列，且同一个旧值的副本仍连成一段**。因为最终是排列，每个旧值只剩一个副本，所以只需保证 $k$ 个旧值的环序。 3. 被替换的两个数**可以相等，也可以是已经出现过的数**（题目只说"替换成 $1\sim N$ 的整数"）。这正是 std 里 $C$ 的下标可能为负、返回 0 的原因：把"球数不够"（即间隔无法都塞满 2 个旧值）的情形自然排除。 4. $n=4$ 必须特判：平移 1 位可达，导致"除以 2"不成立，直接 $24$。 5. 复杂度：预处理阶乘/逆元、一次线性扫描，$O(n)$ 时间、$O(n)$ 空间。 --- ## 7. 一句话总结各分支 设 $k$ 为块数（不同值的个数）： - 有值不连续 → $0$；全是 1 次 → $1$；全相同 → $n!$；最大块长 $\le 2$ → $0$； - $k=n-2$：$n=4$ 时为 $24$，否则 $4(n-2)n$（$n>4$ 偶数再除 2）； - $k\le n-3$：$\dfrac{n!}{(k-1)!}-\sum_{i=1}^{k} m!\,f(\text{ball}_i,m)$，其中 $m=n-k$，$\text{ball}_i=k-i+2\ (i\ge2)$、$\text{ball}_1=k$，$f(x,m)=\binom{x-m-1}{m-1}$。 这就是 std 的完整逻辑；三组样例和 fx4–fx6 都对得上。 ::::