题解 P7327 【Dream and Discs】

Alex_Wei · 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 之和除以方案总数。

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

写在开头的一些定义：

下文中，定义 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。