自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:28:49，当前版本为作者最后更新于2021-02-06 20:24:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目传送门。

题意简述：有 $n$ 个数 $a_1,a_2,\cdots a_n$，等概率选取区间 $P_1,S_1\subseteq [1,n]$，$P_2\subseteq P_1$，$S_2\subseteq S_1$。定义 $f(X,Y)$ 为互不相同的 $a_i\ (i\in X,a_i\in Y)$ 的个数，求 $\Delta=F(P_1,S_1)-F(P_2,S_2)$ 的等权重平均，即所有可能方案的 $\Delta$ 之和除以方案总数。

$1\leq n,a_i\leq 5\times 10^5$。

挺不错的题目。不过官方题解稍显简略，较难理解，我写个易懂点的。

---

写在开头的一些定义：

下文中，定义 $s_i$ 表示前 $i$ 个正整数之和，即 $\sum_{j=1}^ij$；定义 $sq_i$ 表示前 $i$ 个正整数的平方和，即 $\sum_{j=1}^ij^2$。

---

首先假设 $a_i$ 互不相同，那么显然每个数对答案的贡献独立。对于第 $i$ 个数 $a_i$，我们单独讨论其贡献。

• 先求 $a_i$ 对 $F(P_2,S_2)$ 的贡献：所有 $i\in P_2,a_i\in S_2$ 的方案总数。

  不难发现对编号 $i$ 的限制与对数值 $a_i$ 的限制是独立的。那么根据乘法原理，它可以写成 $f_2(i)\times g_2(a_i)$ 的形式，其中 $f_2(i)$ 表示 $i\in P_2$ 的方案总数，$g_2(a_i)$ 表示 $a_i\in S_2$ 的方案总数。同时，又因为 $P_2$ 与 $S_2$ 的定义相同，所以函数 $f_2$ 与 $g_2$ 等价，即 $f_2=g_2$。

  根据 $f_2$ 和 $S_2$ 的定义，$f_2(i)$ 表示 $i\in P_2\subseteq P_1\subseteq [1,n]$ 的总情况数。不妨反过来考虑，将其定义为在位置 $i$ 两侧嵌套两层括号的总方案数。不难发现左右括号相互独立。先考虑左括号：当第一层左括号在 $j$ 两侧时，第二层括号只能套在 $[1,j]$ 的左侧，即 $\sum_{j=1}^ij$，即 $s_j$。同理可求得右括号的方案数为 $s_{n-j+1}$。

  实际上，我是先打表找出规律才想到了这个实际意义。

  这样我们就有了 $f_2$ 的表达式，即 $f_2(i)=s_is_{n-i+1}$。由此推出 $a_i$ 对 $F(P_2,S_2)$ 的贡献，即 $f_2(i)f_2(a_i)=s_is_{n-i+1}s_{a_i}s_{n-a_i+1}$。

• 再求 $a_i$ 对 $F(P_1,S_1)$ 的贡献：所有 $i\in P_1,a_i\in S_1$ 的方案总数。注意此时每一个区间 $P_1(S_1)$ 并不是只计算一次，还应考虑到其子区间 $P_2(S_2)$ 的个数。

  如法炮制，设贡献为 $f_1(i)\times g_1(a_i)$，其中 $f_1(i),g_1(a_i)$ 分别表示 $i\in P_1,a_i\in S_1$ 的情况总数。梅开二度， 同理可得 $f_1=g_1$。根据其实际意义，枚举 $P_1$ 左端点 $l\ (l\leq i)$ 和右端点 $r\ (i\leq r)$，再乘上其子区间个数，可得表达式：

  $$f_1(i)=\sum_{l=1}^i\sum_{r=i}^n\binom{r-l+2}{2}.$$

  注意此处 $r-l+2$ 是因为区间 $P_1$ 长度为 $r-l+1$，而长度为 $len$ 的区间共有 $\binom{len+1}{2}$ 个子区间。将 $\dfrac{1}{2}$ 提出，上式即：

  $$\frac{1}{2}\sum_{l=1}^i\sum_{r=i}^n(r-l+2)(r-l+1). $$

  拆开，可以得到：

  $$\frac{1}{2}\sum_{l=1}^i\sum_{r=i}^nr^2+l^2-2lr+3r-3l+2. $$

  别跟我说这你不会 $\mathcal{O}(n)$ 预处理 $\mathcal{O}(1)$ 求。 分别化简一下，实际上就是：

  $$\begin{aligned}2f_1(i)=&i(sq_n-sq_{i-1})+sq_i(n-i+1)-2s_i(s_n-s_{i-1})\\&+3i(s_n-s_{i-1})-3s_i(n-i+1)+2i(n-i+1)\end{aligned}. $$

  大功告成，这样 $a_i$ 对 $F(P_1,S_1)$ 的贡献即为 $f_1(i)f_1(a_i)$。

---

看似我们已经成功解决了这道题目，但实际上并没有。注意到题目并没有保证 $a_i$ 互不相同。

假设如果有多个相等的数 $a_{i_1}=a_{i_2}=\cdots=a_{i_c}$ 同时满足条件，那么不妨设只有最左边的数会对答案产生贡献。 但即便是这样，也不得不更新一下 $f_1,f_2$ 的求法。

• 实际上，只有对位置上的限制的总情况 $(i\in P_1(P_2))$ 需要重新计算，而对数值上的限制 $(a_i\in S_1(S_2))$ 并不需要，读者可自行思考。

根据上述假设，不难发现如果 $a_i=a_j\ (i<j)$，那么 $a_j$ 对所有左端点在 $i$ 左边的 $P_1(P_2)$ 都不会产生贡献。因此我们设 $f_1'(pre,i)$ 表示 $P_1$ 左端点在 $pre$ 右侧的总情况数。有了求 $f_1$ 的经验，不难写出 $f_1'$ 的表达式：

$$f_1'(pre,i)=\sum_{l=pre+1}^i\sum_{r=i}^n\binom{r-l+2}{2} $$

对比 $f_1(i)$，可以发现 $f_1'$ 相较于 $f_1$ 只有左端点 $l$ 的下界改变，即$f_1(i)=f_1'(1,i)$。类似的，不难得到其化简后的结果，方便 $\mathcal{O}(1)$ 计算。请读者自行推导，此处不再赘述。

因此，$a_i$ 对 $F(P_1,S_1)$ 的贡献可以写为 $f_1'(pre_i,i)\times f_1(a_i)$，其中 $pre_i$ 为在 $a_i$ 之前与 $a_i$ 相等的最右边一个数的位置，若不存在则为 $0$。

同理，不难推出 $f_2'(pre,i)$ 的表达式：因为 “嵌套的第一层左括号” 只能在 $pre$ 右边，$i$ 左边，因此可写出 $f_2'(pre,i)=\sum_{j=pre+1}^ij$。同样的，观察 $f_2(i)$，可以发现 $f_2'$ 相较于 $f_2$ 只有左端点 $l$ 的下界改变，即 $f_2(i)=f_2'(1,i)$。

综上，$a_i$ 对答案的贡献可以写为 $f_1'(pre_i,i)\times f_1(a_i)-f_2'(pre_i,i)\times f_2(a_i)$。

---

结束了吗？还差一点。求出了 $a_i$ 的总方案数，还需要求 $P_1,P_2,S_1,S_2$ 的总方案数。由于 $P_1,P_2$ 与 $S_1,S_2$ 在定义上等价，因此可以单独算出 $P_1,P_2$ 的总方案数 $cnt$，再将其平方即可得到四个区间的总方案数。这也是为什么三个样例的分母都是平方数，给分数不约分的良心出题人点赞！

不妨枚举 $P_1$ 的长度 $len$，则 $P_1$ 共有 $n-len+1$ 种情况，此时其子区间 $P_2$ 有 $\binom{len+1}{2}$ 中情况。根据定义，不难发现 $s_i$ 等价于 $\binom{i+1}{2}$，因此有：

$$cnt=\sum_{i=1}^n(n-i+1)s_i.$$

至此，本题被我们解决。

---

时间复杂度：预处理 $\mathcal{O}(n)$，计算每个数的贡献 $n\times\mathcal{O}(1)=\mathcal{O}(n)$，计算总情况数 $\mathcal{O}(n)$。

因此，总时空复杂度 $\mathcal{O}(n)$。

---

代码说明：

• cals/calsq(l,r) 表示求 $s(sq)$ 在 $[l,r]$ 上的和。
• f1/f2(l,k) 表示求 $f_1'(f_2')(l-1,k)$。注意代码与实际定义的区别（代码中 $pre_i$ 表示在 $a_i$ 前与 $a_i$ 相同的最右边的数的位置 $+1$）

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int mod=1e9+7;
const ll iv2=mod+1>>1;

ll ksm(ll a,ll b){
	ll s=1,m=a;
	while(b){
		if(b&1)s=s*m%mod;
		m=m*m%mod,b>>=1;
	} return s;
} ll inv(ll x){return ksm(x,mod-2);}

const int N=5e5+5;
ll n,a,ans,cnt,buc[N],s[N],sq[N];
ll cals(ll l,ll r){return (s[r]-s[l-1]+mod)%mod;}
ll calsq(ll l,ll r){return (sq[r]-sq[l-1]+mod)%mod;}
ll f1(ll l,ll k){
	return ((calsq(l,k)*(n-k+1)+calsq(k,n)*(k-l+1)
			-2*cals(l,k)*cals(k,n)%mod-3*cals(l,k)*(n-k+1)%mod
			+3*cals(k,n)*(k-l+1)+2*(n-k+1)*(k-l+1))%mod+mod)*iv2%mod;
} ll f2(ll l,ll k){return cals(l,k)*s[n-k+1]%mod;}

int main(){
	cin>>n;
	for(ll i=1;i<=n;i++)s[i]=(s[i-1]+i)%mod,sq[i]=(sq[i-1]+i*i)%mod;
	for(ll i=1,pre;i<=n;i++){
		scanf("%lld",&a),pre=buc[a]+1,buc[a]=i;
		ans=(ans+f1(pre,i)*f1(1,a)-f2(pre,i)*f2(1,a)%mod+mod)%mod;
		cnt=(cnt+(n-i+1)*s[i])%mod;
	} cout<<ans*inv(cnt*cnt%mod)%mod<<endl;
	return 0;
}

长 篇 巨 著。

感觉做完这题水平提升了一大截。

看在这么详细的份上，看懂了就点个赞吧 qwq。