题解：P16923 [JLCPC 2026] 水晶城堡

· · 题解

题解区做法有点单一啊，来点做法整合。

统一步骤：先考虑一个长度为 N 的序列上答案是什么。然后发现式子只和 t（出现次数数组）有关，直接使用莫队维护即可。

方法 1：

不妨将 \langle1,1,2\rangle 这种排列计算多次，去掉相同元素排列的对答案的影响，方便计算。

注意到：记 X 为随机排列的连续段数量，Y 为随机排列的相邻的颜色相同的数量，那么 X+Y=N。于是 E(X)=E(N-Y)=N-E(Y)。

如果你注意到了上面的东西，那么这道题在十分钟内即可通过，否则，你会像我一样死磕一整场 /ll。

接着上面的步骤，记 t_i 表示序列中值为 i 的数的个数，我们有：

\begin{aligned} \mathbb{E}(Y)&=\mathbb{E}\left(\sum_{i=1}^{N-1}[a_{p_i}=a_{p_{i+1}}]\right) \\&=\mathbb{E}\left(\sum_{c=1}^N\sum_{i=1}^{N-1}[a_{p_i}=a_{p_{i+1}}=c]\right) \\&=\mathbb{E}\left(\sum_{c=1}^N\sum_{i=1}^{N-1}[a_{p_i}=c\land a_{p_{i+1}}=c]\right) \\&=\frac{\sum_{c=1}^N\binom{t_c}{2}\times2!\times(N-1)\times(N-2)!}{N!} \end{aligned}

解释一下最后一步：从颜色为 c 的数中选两个作为相邻的颜色相同的部分，这个部分可以放在 N-1 个位置，剩下的 N-2 个位置可以随便放东西。然后除以可能的排列数 N!。

之后用莫队维护即可。

方法 2：

来自 JiaoYou。

一个长度为 N 序列 A 的颜色段数量等于 1+\sum_{i=1}^{N-1}[A_i\neq A_{i+1}]。

期望即为：

\begin{aligned} &\mathbb{E}\left(1+\sum_{i=1}^{N-1}[A_i\neq A_{i+1}]\right) \\=&1+\mathbb{E}\left(\sum_{i=1}^{N-1}[A_i\neq A_{i+1}]\right) \\=&1+\sum_{i=1}^{N-1}\mathbb{P}(A_i\neq A_{i+1})\times1 \\=&1+(N-1)\mathbb{P}(A_i\neq A_{i+1}) \end{aligned}

最后一步是因为每个位置的概率实际上是相同的。

考虑计算 \mathbb{P}(A_i\neq A_{i+1})。

一种化简方式是：

\begin{aligned} \mathbb{P}(A_i\neq A_{i+1})&=\frac{N(N-1)-\sum_{c=1}^N t_c(t_c-1)}{N(N-1)} \\&=\frac{N^2-N-\sum_c t_c^2+\sum_c t_c}{N(N-1)} \\&=\frac{N^2-\sum_c t_c^2}{N(N-1)} \end{aligned}

另一种化简方式是：

\begin{aligned} \mathbb{P}(A_i\neq A_{i+1})&=1-P(A_i=A_{i+1}) \\&=1-\frac{\sum_{c=1}^N 2\binom{t_c} {2}(N-2)!}{N!} \end{aligned}

之后用莫队维护即可。

方法 3：

来自 AuCodingFrogHoward。

一个不需要用连续段转换技巧的方法。

我们将颜色段数量按照颜色拆开，对于每个颜色，枚举它能构成的颜色段个数，并统计满足条件的排列数，相乘后相加即可。

记 \text{part}(n,m):=\binom{n-1}{m-1} 表示 n 个数划分成 m 段的方案数。记 \text{gap}(n,m):=\binom{n+m-1}{m-1} 表示不定方程 \sum_{i=1}^n x_i=m 的非负整数解。

那么，我们有：

N!\times\mathbb{E}[X]=\sum_{c=1}^{N}\sum_{i=1}^{t_c}i\times\text{part}(t_c,i)\times t_c!(N-t_c)!\times\text{gap}(N-t_c-(i-1),i+1)

解释一下，先把 t_c 个元素分为 i 个颜色段。然后乘上 t_c!(N-t_c)! 把可重元素赋上顺序。由于我们需要满足 i 个颜色段之间存在其他的数，两边可以有元素，也可以没有元素，于是可以先在 i-1 个间隔里面加入一个元素，再将剩下的数放入 i+1 个空里面（可以有空不放）。

这里要莫队维护还需要多拆一下式子。

\begin{aligned} &\sum_{c=1}^{N}\sum_{i=1}^{t_c}i\times\text{part}(t_c,i)\times t_c!(N-t_c)!\times\text{gap}(N-t_c-(i-1),i+1) \\=&\sum_{c=1}^{N}\sum_{i=1}^{t_c}i\times t_c!(N-t_c)!\times\binom{N-t_c+1}{i}\times\binom{t_c-1}{i-1} \\=&\sum_{c=1}^{N}t_c!(N-t_c)!\sum_{i=1}^{t_c}i\times\binom{N-t_c+1}{i}\times\binom{t_c-1}{i-1} \\=&\sum_{c=1}^{N}t_c!(N-t_c)!\sum_{i=1}^{t_c}(N-t_c+1)\times\binom{N-t_c}{i-1}\times\binom{t_c-1}{i-1} \\=&\sum_{c=1}^{N}(N-t_c+1)\times t_c!(N-t_c)!\sum_{i=0}^{t_c-1}\binom{N-t_c}{i}\binom{t_c-1}{i} \\=&\sum_{c=1}^{N}(N-t_c+1)\times t_c!(N-t_c)!\binom{N-1}{t_c-1} \end{aligned}

到这里就可以用莫队维护了。

当然，你也可以进一步的拆成：

\begin{aligned} \mathbb{E}[X]&=\frac{1}{N!}\sum_{c=1}^{N}(N-t_c+1)\times t_c!(N-t_c)!\binom{N-1}{t_c-1} \\&=\frac{1}{N!}\sum_{c=1}^{N}(N-t_c+1)\times t_c!(N-t_c)!\times\frac{(N-1)!}{(t_c-1)!(N-t_c)!} \\&=\frac{1}{N}\sum_{c=1}^{N}(N-t_c+1)t_c \end{aligned}

其实这个和上述方法等价。

方法 4：

和上面的方法 3 大致相同，既然我们划分颜色段的时候都没有考虑顺序，那就可以直接按照相同元素之间没有顺序区分来考虑。

那么，我们有：

\frac{N!}{\prod_{c=1}^N t_c!}\times\mathbb{E}[X]=\sum_{c=1}^{N}\sum_{i=1}^{t_c}i\times\text{part}(t_c,i)\times\text{gap}(N-t_c-(i-1),i+1)\times\frac{(N-t_c)!}{\prod_{w\neq c} t_w!}

需要注意的是，不同元素之间仍有区别，于是需要乘上 \frac{(N-t_c)!}{\prod_{w\neq c} t_w!} 才是对的。

细心的你容易发现，这个式子化简一下就和上面的方法 3 没有区别了。

只写了方法 1，不过其他的也差不多。

莫队复杂度为 O(n\sqrt{q})。

:::success[代码（方法 1）]

/*

Start Code At 2026/8/9 8:25:08 .

Code by Bestart (luogu uid : 1062290) .

*/

#include <bits/stdc++.h>
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf , 1 , fread_cnt , stdin) , p1 == p2) ? EOF : *p1 ++)

using namespace std ;

using db    = double ;
using i128  = __int128 ;
using ll    = long long ;
using ldb   = long double ;
using uint  = unsigned int ;
using ui128 = unsigned __int128 ;
using ull   = unsigned long long ;

#define inline
//#define int long long

mt19937 rnd( chrono :: system_clock :: now() .time_since_epoch() .count() ) ;

const uint fread_cnt = 1 << 20 | 10 ;
const uint mod = 998244353 ;
const uint MN = 1e5 + 10 ;
const uint MQ = 1e5 + 10 ;
const int inf = 1e9 + 7 ;
//const ll inf = 1e18 ;

char buf[fread_cnt] , *p1 = buf , *p2 = buf ;

template <typename T = int>
inline T read()
{
    bool f = 0 ;  T x = 0 ;  char ch = gc() ;

    while(ch < '0' || ch > '9')  f ^= ch == '-' , ch = gc() ;
    while(ch >= '0' && ch <= '9')  x = (x << 3) + (x << 1) + (ch ^ 48) , ch = gc() ;

    return f ? -x : x ;
}

inline uint qpow (ull a , ull b = mod - 2 , uint p = mod) 
{
    uint res = 1 ;
    while(b) 
    {
        if(b & 1)  res = res * a % p ;
        a = a * a % p , b >>= 1 ;
    }
    return res ;
}

uint ji[MN] , nji[MN] ;
inline void init (uint n = MN-1) 
{
    ji[0] = nji[0] = 1 ;
    for(uint i = 1 ; i <= n ; ++ i)  ji[i] = 1ull * ji[i-1] * i % mod ;
    for(uint i = 1 ; i <= n ; ++ i)  nji[i] = qpow(ji[i]) ;
}

uint n , m , bize , res , a[MN] , t[MN] , bl[MN] , ans[MQ] ;

struct ques {
    uint l , r , ide ;
} q[MQ] ;

inline bool cmp (ques q1 , ques q2) 
{
    return bl[q1.l] == bl[q2.l] ? bl[q1.l] & 1 ? q1.r < q2.r : q1.r > q2.r : bl[q1.l] < bl[q2.l] ;
}

inline void add (uint x) 
{
    res = (res + t[a[x]]) % mod , ++ t[a[x]] ;
}

inline void del (uint x) 
{
    -- t[a[x]] , res = (res + mod - t[a[x]]) % mod ;
}

inline bool solve()
{

    for(uint i = 1 ; i <= n ; ++ i)  a[i] = bl[i] = t[i] = 0 ;
    for(uint i = 1 ; i <= m ; ++ i)  ans[i] = q[i] .l = q[i] .r = q[i] .ide = 0 ;
    n = m = bize = res = 0 ;

    cin >> n >> m , bize = n / sqrt(m) ;
    for(uint i = 1 ; i <= n ; ++ i)  cin >> a[i] , bl[i] = i < bize ? 1 : bl[i-bize] + 1 ;
    for(uint i = 1 ; i <= m ; ++ i)  cin >> q[i] .l >> q[i] .r , q[i] .ide = i ;
    sort(q+1 , q+m+1 , cmp) ;
    res = 0 ;
    for(uint i = 1 , l = 1 , r = 0 ; i <= m ; ++ i) 
    {
        while(r < q[i] .r)  add(++r) ;
        while(l > q[i] .l)  add(--l) ;
        while(r > q[i] .r)  del(r--) ;
        while(l < q[i] .l)  del(l++) ;
        ans[q[i] .ide] = (r-l+1 + mod - res * 2ull * ji[r-l+1-1] % mod * nji[r-l+1] % mod) % mod ;
    }
    for(uint i = 1 ; i <= m ; ++ i)  cout << ans[i] << '\n' ;

    return 0 ;
}

signed main()
{
//  freopen("rune.in" , "r" , stdin) ;
//  freopen("rune.out" , "w" , stdout) ;

    cin.tie(0) -> sync_with_stdio(0) ;

//  system("fc .out .ans") ;

    int t = 1 ;   init(1e5) , cin >> t ;   while(t --)  solve() ;

//  while(!solve()) ;

//  solve() ;

    return 0 ;
}

:::