题意简述

给定一个长度为 $N$ 的颜色序列，$M$ 次询问区间 $[L,R]$ 中随机取两只袜子颜色相同的概率。 询问的 $L,R$ 经过加密，需要在线解密。

概率计算

设区间 $[L,R]$ 长度为 $len = R-L+1$。

总方案数：

total

( l e n 2 )

l e n ( l e n − 1 ) 2 total=( 2 len ​ )= 2 len(len−1) ​

设颜色 $c$ 在区间中出现次数为 $cnt_c$，那么颜色 $c$ 的贡献方案数为 $\binom{cnt_c}{2}$。

相同颜色的总方案数：

same

∑ c ( c n t c 2 )

∑ c c n t c ( c n t c − 1 ) 2 same= c ∑ ​ ( 2 cnt c ​

​ )= c ∑ ​

2 cnt c ​ (cnt c ​ −1) ​

概率为：

same total

∑ c n t c ( c n t c − 1 ) l e n ( l e n − 1 ) total same ​

len(len−1) ∑cnt c ​ (cnt c ​ −1) ​

问题转化

我们需要快速计算：

∑ c c n t c 2 − ∑ c c n t c c ∑ ​ cnt c 2 ​ − c ∑ ​ cnt c ​

注意 $\sum_{c} cnt_c = len$，所以：

same

∑ c n t c 2 − l e n same=∑cnt c 2 ​ −len 因此问题转化为：快速求区间内各颜色出现次数的平方和。

在线与数据范围

$N,M \le 50000$

询问在线解密，无法离线排序

需要支持快速区间询问 $\sum cnt_c^2$

解法：莫队算法

莫队算法可以在 $O(N\sqrt{M})$ 时间内处理所有询问，适合本题数据范围。

莫队思路

将序列分块，块大小约 $\sqrt{N}$。

将询问按左端点所在块排序，块相同时按右端点排序。

用两个指针 $l,r$ 维护当前区间，并维护 $sum = \sum cnt_c^2$。

当加入一个颜色 $x$ 时：

s u m −

c n t x 2 sum−=cnt x 2 ​

c n t x +

1 cnt x ​ +=1 s u m +

c n t x 2 sum+=cnt x 2 ​

当删除一个颜色 $x$ 时：

s u m −

c n t x 2 sum−=cnt x 2 ​

c n t x −

1 cnt x ​ −=1 s u m +

c n t x 2 sum+=cnt x 2 ​

对于每个询问，$same = sum - len$，$total = \frac{len(len-1)}{2}$。

输出前约分。

时间复杂度

排序 $O(M\log M)$

莫队转移 $O(N\sqrt{M})$

总复杂度可接受 $N,M \le 50000$

示例代码（框架） cpp #include <bits/stdc++.h> using namespace std; using ll = long long; const int MAXN = 50005;

int n, m, block; int c[MAXN], cnt[MAXN]; ll sum;

struct Query { int l, r, id; bool operator<(const Query &other) const { if (l / block != other.l / block) return l < other.l; return r < other.r; } } q[MAXN];

ll ans1[MAXN], ans2[MAXN]; // 分子分母

void add(int pos) { sum -= (ll)cnt[c[pos]] * cnt[c[pos]]; cnt[c[pos]]++; sum += (ll)cnt[c[pos]] * cnt[c[pos]]; }

void del(int pos) { sum -= (ll)cnt[c[pos]] * cnt[c[pos]]; cnt[c[pos]]--; sum += (ll)cnt[c[pos]] * cnt[c[pos]]; }

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

int main() { scanf("%d%d", &n, &m); block = sqrt(n); for (int i = 1; i <= n; i++) scanf("%d", &c[i]);

int lastans = 0;
for (int i = 1; i <= m; i++) {
    int le, re;
    scanf("%d%d", &le, &re);
    // 解密
    int L = (le + lastans - 1) % n + 1;
    int R = (re - lastans - 1) % n + 1;
    if (L > R) swap(L, R);
    q[i] = {L, R, i};
}

// 莫队处理
sort(q + 1, q + m + 1);
int l = 1, r = 0;
for (int i = 1; i <= m; i++) {
    int L = q[i].l, R = q[i].r;
    if (L == R) {
        ans1[q[i].id] = 0;
        ans2[q[i].id] = 1;
        continue;
    }
    while (l > L) add(--l);
    while (r < R) add(++r);
    while (l < L) del(l++);
    while (r > R) del(r--);
    
    ll len = R - L + 1;
    ll same = sum - len;
    ll total = len * (len - 1) / 2;
    ll g = gcd(same, total);
    ans1[q[i].id] = same / g;
    ans2[q[i].id] = total / g;
    lastans = same / g + total / g; // 用于下次解密
}

for (int i = 1; i <= m; i++) {
    printf("%lld/%lld\n", ans1[i], ans2[i]);
}

return 0;

}

总结

核心是求区间颜色出现次数平方和。

莫队算法处理在线区间询问。

概率公式化简为 $\frac{\sum cnt_c^2 - len}{len(len-1)}$。

注意 $L=R$ 时输出 0/1。