题解：AT_arc187_e [ARC187E] Replace Triplets

DSD486 · 2026-11-11 08:08:08 · 题解

我们是 CQYC。

教练说这是铜牌题，但实际考下来我们却感觉像银牌题。

可能是因为题解思路的关系吧。

此篇会讲的很详细。

每部分内容用 --- 分隔。

题目这个操作无疑是奇怪的，所以我们定义“反向操作”为将相邻三个数替换为其中的一个，比如 (x , y , z) \longrightarrow (x , x , x)。

容易发现一个排列 P 能从 A 得到，当且仅当可以通过反向操作，把 P 变成 A。

结论 1：环形的 A 中，每个数字必须是连续的，否则可生成 P 数量为 0。

::::info[证明]

注意反向操作从原三个数中选一个替换。

那么它只能添加或修改相邻的数。

因为 P 最终每个数只有一个，所以用反向操作不可能产生一种数的多个区间。

::::

代码中先将这种无解判掉，之后的讨论也基于有解。

结论 2：在 P 中，A 原来出现过的数字，其环形相对顺序必须和 A 中相同。

稍微手玩下即可得。

我们定义：

• 旧数字为 A 中出现的数。

• 新数字为 A 中未出现的数。

先判断几个特殊情况：

结论 3.1：至少存在两个新数字，它们在 P 中的环形距离不超过 2。

::::info[证明]

考虑正向操作，最后一步一定是将 (x , x , x) \longrightarrow (x , y , z)。

其中 y , z 显然是新数字。

距离为 2 即 (y , x , z)。

::::

先分讨。

若块长形似 2 + 2 + 1 + 1 \dots，依旧答案为 0。

否则块长形似 3 + 1 + 1 \dots。

此时设经历若干次正向操作后，块长为 3 的块，最后一次操作为 (x , x , x) \longrightarrow (x , y , z)。

而 y,z 是唯二的新数字，所以由结论 3.1，得它们在 A 中的环形距离不超过 2。

此时 y 有 n 个位置可选，z 有 4 种，再限制块的位置有 n-2 种，得 4n(n - 2)。

但是这些排列并不一定全部可达。

给出形式化证明，具体手玩一下。

::::info[证明]{open}

考虑反向操作。

最后一次正向操作对应的三个位置，反向之后会形成一个三连块。

设 s 为这个三连块的起始位置，j 为这个三连块所代表的旧数字在旧数字环形顺序中的编号。

为了还原到 A，我们需要让三连块最终回到原来长度为 3 的块的位置，同时代表正确的旧数字。

反向移动后 (x,x,y)\longrightarrow(y,y,y)，s \leftarrow s + 1 , j \leftarrow j + 1。

假设总共移动 t 次。

那么需要满足 s+t\equiv0\pmod n，j+t\equiv0\pmod k.

根据中国剩余定理，这两个方程有解的充要条件是：s\equiv j\pmod{\gcd(n,k)}。

又因为 k=n-2，所以 \gcd(n,k) = \gcd(n,n - 2) = \gcd(n,2)。

继续分讨。

任意 s,j 都满足条件，所以所有候选排列都可以得到，则 Ans=4n(n-2)。

现在要求 s\equiv j\pmod2，即位置编号和旧数字编号必须具有相同的奇偶性。

由于 n,k 都是偶数，因此所有候选排列中恰好有一半满足条件。

所以 Ans=2n(n-2)。

注意 n = 4 要特判。

此时 A 形如 (1 , 1 , 1 , 3)。显然具体数值不影响。

手玩发现所有排列都可达，Ans = 4! = 24。

感性理解的话，此时两个新数字对应的长度为 3 的窗口可能有两种选择，可以选择合适的窗口作为三连块，所以合法。

::::

结论 3.2：只要旧数字环形顺序正确，并且存在两个新数字的环形距离不超过 2，这个排列就一定可以得到。

注意此时 m \ge 3。

:::info[证明]

虽然结论说的有点绕，但 3.2 其实为 3.1 的充分性证明。

考虑反向操作可以做到什么，依旧有 (x , x , x)。

第一种：合并，(x , x , x , y) \longrightarrow (x , x , x , x)。

第二种：转换，(x , x , x , y) \longrightarrow (x , y , y , y)。

为了符合环形顺序，我们将一个三连块移动时，如果遇到旧数字，那么就转换。遇到新数字就合并。

这里的初始三连块是两个新数加一个旧数变的，显然可以找到。

在执行完上面的所有合并与转换后，P 中只剩旧数了，

并且原顺序不变。

发现此时块长是可以随意调整的。

因为就算初始合并了两个新数，还有 \ge 1 个的新数，它们提供块长 \pm 1 的改变，再加上其余每次往旁边蠕动一格，块长就对了。

同时，它们还可以让上文的 s \leftarrow s + 1，j 不变，那么顺序也没问题了，必定有解。

:::

计数。

先只考虑环形顺序的限制，考虑钦定 1（一个旧数字）在下标 x，有 n 种选择。

还剩下 n - 1 个位置，从中选出 k - 1 个放数，用组合数保证顺序，则 \binom{n-1}{k-1} 种。

然后剩下 m 个空位，任意放新数字，则 m! 种。

那么：

展开化简：

此时减去不可得排列。

由结论 3.2，需要减去任意两个新数字的环形距离都至少为 3 的排列。

考虑此时排列形如 N , O , O , N , O , O , N , O , O。其中 N 为新数字，O 为旧数字。

那么等同于有 k 个数，填入 m 个空隙，每个空隙至少放两个。

由隔板法得方案数为 \binom{k-2m+m-1}{m-1} = \binom{k-m-1}{m-1}。

这里我们只统计了旧数字的间隔，还要计数新数字。

依旧钦定 1（一个新数字）在下标 x，有 n 种选择。

剩下 m - 1 个新数字任意排列，注意不选位置，方案数为 (m-1)!。

再钦定 1 后的旧数字 2，有 k 种，因为旧数字顺序定了，所以所有都定了。

那么：

化简随意。

::::success[Code]

#include <bits/stdc++.h>
#define int long long
#define PII pair < int , int >
#define x first
#define y second
using namespace std ; 
bool bbb ; 

const int N = 1e7 + 5 , P = 998244353 ; 
int n , a[N << 1] ; 
bool vis[N] ; 
int fac[N] , inv[N] ; 
int qpow(int a , int b){
    int res = 1 ; 
    while(b){
        if(b & 1) res = res * a % P ; 
        b >>= 1 , a = a * a % P ; 
    }
    return res ; 
}
void init(int n){
    fac[0] = 1 ; 
    for(int i = 1 ; i <= n ; i++) fac[i] = fac[i - 1] * i % P ; 
    inv[n] = qpow(fac[n] , P - 2) ; 
    for(int i = n - 1 ; ~i ; i--) inv[i] = inv[i + 1] * (i + 1) % P ; 
}
int C(int n , int m){
    if(n < 0 || m < 0 || n < m) return 0 ; 
    return fac[n] * inv[m] % P * inv[n - m] % P ; 
}
int f(int x , int m){ return C(x - m - 1 , m - 1) ; }

bool eee ; 
signed main(){
//  freopen("fx.in" , "r" , stdin) ; 
//  freopen("fx.out" , "w" , stdout) ; 
    ios :: sync_with_stdio(0) ; 
    cin.tie(0) ; cout.tie(0) ; 
    cerr << "Memory: " << abs((char*)&eee - (char*)&bbb) / 1024.0 / 1024.0 << " MB\n" ; 
    init(N - 5) ; 
    cin >> n ; 
    for(int i = 1 ; i <= n ; i++) cin >> a[i] , a[i + n] = a[i] ; 
    int x = n , k = 0 , mx = 0 , lat = x ; 
    while(x > 1 && a[x - 1] == a[n]) -- x ; 
    for(int i = x ; i < n + x ; i++) if(a[i] != a[i - 1]){
        if(vis[a[i]]) return cout << "0\n" , 0 ; 
        vis[a[i]] = 1 , ++ k ; 
        mx = max(mx , i - lat) , lat = i ; 
    }
    mx = max(mx , n + x - lat) ; 
    if(k == n) return cout << "1\n" , 0 ; 
    if(k == 1) return cout << fac[n] << '\n' , 0 ; 
    if(mx <= 2) return cout << "0\n" , 0 ; 
    if(k == n - 2){
        if(n == 4) return cout << "24\n" , 0 ; 
        return cout << 4 * (n - 2) * n % P * ((n > 4) && (n % 2 == 0) ? qpow(2 , P - 2) : 1) % P << '\n' , 0 ; 
    }
    int ans = fac[n] * inv[k - 1] % P , m = n - k ; 
    (ans -= n * k % P * fac[m - 1] % P * C(k - m - 1 , m - 1) % P - P) %= P ; 
    cout << ans << '\n' ; 
    return 0 ; 
}
/*

6
1 2 3 3 1 1

5
1 2 1 1 1

5
3 1 3 4 1

4
4 4 4 4

24

10
1 1 1 8 8 8 7 7 7 10

6
1 2 2 2 1 1

*/

::::