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

· · 题解

前言

本题被放在了集训 NOIP 模拟赛的 T1。

Solution

考虑对于一个给定序列 x_1,x_2,\ldots,x_k，求其色段的数量，很显然答案是 1+\sum_{i=1}^{k-1}[x_i\neq x_{i+1}]，即相邻不同数的对数。

考虑对于 p 位置，打乱后满足 x_p\neq x_{p+1} 的概率是多少，我们记 cnt_i 表示 i 的个数，tot 表示总颜色数，那么有：

P[x_p\neq x_{p+1}]=\sum_{i=1}^{tot}\frac{cnt_i}{k}\times \frac{k-cnt_i}{k-1}

上式的含义是先在 p 位置选定颜色 i，然后要求 p+1 位置出现 i 以外的颜色。

注意到分母可以提出来：

\frac{\sum_{i=1}^{tot}cnt_i\times (k-cnt_i)}{k(k-1)}=\frac{\sum_{i=1}^{tot}cnt_i\times k-{cnt_i}^2}{k(k-1)}

进一步地，由于 \sum_{i=1}^{tot}cnt_i=k，所以原式为：

\frac{k^2-\sum_{i=1}^{tot}{cnt_i}^2}{k(k-1)}

显然这个式子和 p 无关，所以对于每个位置 p，x_p\neq x_{p+1} 的概率都一样，那么记色段数为 Ans，则有：

E[Ans]=1+(k-1)\times \frac{k^2-\sum_{i=1}^{tot}{cnt_i}^2}{k(k-1)}=1+\frac{k^2-\sum_{i=1}^{tot}{cnt_i}^2}{k}

直接莫队维护即可。

Code

#include<bits/stdc++.h>
#define int long long 
#define YUANSHEN ios_base::sync_with_stdio(0);
#define QIDONG cin.tie(0);
#define inf 1e18
#define endl '\n'
#define mod 998244353
#define frein freopen("rune.in","r",stdin);
#define freout freopen("rune.out","w",stdout);
using namespace std;
const int maxn=1e6+10;

int n,q,pos[maxn],T,cnt[maxn],ans[maxn],now=0,a[maxn];

struct Node{
    int L,R,idx;
    friend bool operator <(Node i,Node j){return (pos[i.L]!=pos[j.L])?(pos[i.L]<pos[j.L]):(pos[i.R]<pos[j.R]);}
}Q[maxn];

void init(){
    now=0; 
    for(int i=1;i<=n;i++)cnt[i]=0;
    int k=sqrt(n),j=1;
    for(int i=1;i<=k;i++)while(j<=i*k)pos[j++]=i;
    while(j<=n)pos[j++]=k+1;
}

int Getinv(int a){
    int res=1,x=mod-2;
    for(;x;x>>=1,a=(a*a)%mod)if(x&1)res=res*a%mod;
    return res;
}

void add(int i){now+=2*cnt[a[i]]+1,cnt[a[i]]++;}
void del(int i){now+=1-2*cnt[a[i]],cnt[a[i]]--;}

signed main(){
    YUANSHEN QIDONG
    frein freout
    cin>>T;
    while(T--){
        cin>>n>>q; init();
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<=q;i++)cin>>Q[i].L>>Q[i].R,Q[i].idx=i;
        sort(Q+1,Q+1+q);
        for(int i=1,L=1,R=0;i<=q;i++){
            while(R<Q[i].R)add(++R);
            while(R>Q[i].R)del(R--);
            while(L<Q[i].L)del(L++);
            while(L>Q[i].L)add(--L);
            ans[Q[i].idx]=(1+(Q[i].R-Q[i].L+1)-now%mod*Getinv(Q[i].R-Q[i].L+1)%mod+mod)%mod;
        }
        for(int i=1;i<=q;i++)cout<<ans[i]<<endl;
    }
    return 0;
}

青紫紫黑的 NOIP 模拟赛好玩吗？