P10792 『SpOI - R1』笑起来最帅的小孩 题解

· · 题解

题目传送门

本题，我感觉，给成黄题有点不对，逆元 + 类快速幂 + 数学（期望，概率）应该是绿。

观前提示

所有部分代码都有

#include <iostream>
#include <cmath>
#define int long long
using namespace std;
const int mod=2007072007;
int x,y;
int Mod(int n){
    return (n%mod+mod)%mod;
}

本题解话可能语无伦次，请见谅。

Tips 您的正确代码炸了的可能原因

简述题意

给定一个数字串，和一个空的序列，将数字串中的数字依次等概率的插入序列中两个数字的间隔或者序列首和序列尾，求最终序列的数排在一起形成的数的期望模 m=2007072007。

期望

何为期望？

举几个例子，如果在一个事件中，结果出现 1,2,3,4,5 的概率是均等的，均为 20\%，那么，这个事件的期望是 1,2,3,4,5 以 20\% 为权的加权平均数，是 3。也就是说，期望是数据中每个数据以出现概率为权的加权平均数。注意这里的概率并不一定相同，但是和一定为 1。因为“结果是结果可能出现的多种情况之一”是全概率事件（废话）。

概率推导

现在，我们知道想求出结果，就要求出出现各种结果的概率，那就求。

首先，我们假设所有 n 个数字都不相同。那么在 n! 种这些数字的全排列中，每一个排列都对应着一种插入的方法，并且我们发现每种插法出现的概率均为 \displaystyle\frac{1}{n!}，和正好是 1。所以可能出现的情况就是 n 个数的全排列，并且概率均等，均为 \displaystyle\frac{1}{n!}。

有问题，在刚才的证明中我们假设所有数字均不相同，那么如果有相同的数字呢？我们可以将相同的数字标号区分，比如当输入的数字是 1,2,2,2,3 时，我们可以将三个 2 分别标号为 2_1,2_2,2_3，这样就可以用上面的结论。

此时，我们就要求最终的期望了，设最终答案为 ans，n 个数字分别为 a_1\~a_n，最终结果分别为 A_1 \~ A_{n!}。因为每个 a_i 在 n 位中每一位都出现了 (n-1)! 次，所以

\begin{aligned} ans&=\sum_{i=0}^{n!}A_i \times \frac{1}{n!}\\ &=\frac{\sum_{i=0}^{n!}A_i}{n!}\\ &=\frac{\sum_{i=0}^{n}a_i \times (n-1)! \times q(n) }{n!}\\ &=\frac{\sum_{i=0}^{n}a_i \times q(n) }{n} \end{aligned}

其中 q(n) 表示 n 个 1 并在一起形成的数，也就是 \displaystyle\sum_{i=0}^ {n-1}10^i。

这样，想求出最终结果 ans \bmod m，我们实际需要求的就是 (\displaystyle\sum_{i=0}^{n}a_i) \bmod m,q(n) \bmod m 和 \frac{1}{n} \bmod m 的乘积再模 m 的值。

很容易地发现 (\displaystyle \sum_{i=0}^{n}a_i) \bmod m=(\sum_{i=0}^kx_il_i) \bmod m，这部分可以 O(k) 解决。

这部分的代码：

int k;
cin>>k;
int a,l;
int suma=0,n=0,o=0,ans;
for(int i=0;i<k;i++){
    cin>>a>>l;
    n+=l;
    suma+=a*l;
    n%=mod;
    suma%=mod;
}

逆元

刚才我们分析后发现，有一个子问题是 \displaystyle\frac{1}{n} \bmod m，不妨设这个值是 x，所以

\begin{aligned} \frac{1}{n} & \equiv x \pmod m\\ xn & \equiv 1 \pmod m \end{aligned}

这里的 x 就叫做 n 在模 m 意义下的逆元。

如何求 x 呢？

这里我偷懒，贴一个大佬的博客，谢谢。本题中我采用了拓欧的方法。

部分代码

void Eg(int a,int b,int &x,int &y){
    if(b==0){
        x=1,y=0;
    }
    else{
        Eg(b,a%b,y,x);
        y-=a/b*x;
    }
}
int ny(int a){
    Eg(a,mod,x,y);
    return (x%mod+mod)%mod;
}

这样我们只需要求 q(n) \bmod m 了。

类快速幂

怎么求 q(n) \bmod m 呢？

可以用等比数列求和但是别的大佬讲了，我讲一下自己的方法吧

很容易发现一个 q 的递推式：q(i) = q(i-1) \times 10 + 1。所以可以得到以下 O(n) 的代码：

long long s_s1(int n){
    int o=0;
    for(int i=0;i<n;i++){
        o=o*10+1;
        o%=mod;
    }
    return o;
}

然而，这道题的 n 范围是 2 \times 10^9，这肯定会 TLE（实际得分55pts）

观察特点，发现 q 特别像幂函数，可以通过快速幂的二分思想来解决。易得 q 的二分递推式是

q(i)=\begin{cases} 1 &（i=1）\\ q(i/2) \times 10^{n/2}+q(i/2)&(i \bmod 2 = 0)\\ (q(i/2) \times 10^{n/2}+q(i/2)) \times 10+1&(i \bmod 2 = 1 且 i \ne 1) \end{cases}

然后我们再用快速幂去求 10^{n/2} 就好了。

注意这里不能用 pow，会炸 long long，要自己再手打快速幂并取模。

部分代码：

int f_s(int n){//求10^n
    if(n==0)return 1;
    if(n==1)return 10;
    int r=f_s(n/2);
    if(n&1){
        return Mod(Mod(r*r)*10);
    }
    else{
        return Mod(r*r);
    }
}
long long f_s1(int n){//求q(n)
    if(n==1)return 1;
    if(n==2)return 11;
    long long r=f_s1(n/2);
    if(n&1){
        return Mod(Mod(r*Mod(f_s(n/2))+r)*10+1);
    }
    else{
        return Mod(r*Mod(f_s(n/2))+r);
    }
}

复杂度 O(\log n)。

Code

于是我们就可以贴上完整代码了

注：完整代码中的 mod 即为模数 m。

#include <iostream>
#include <cmath>
#define int long long
using namespace std;
const int mod=2007072007;
int x,y;
int Mod(int n){
    return (n%mod+mod)%mod;
}
void Eg(int a,int b,int &x,int &y){
    if(b==0){
        x=1,y=0;
    }
    else{
        Eg(b,a%b,y,x);
        y-=a/b*x;
    }
}
int ny(int a){
    Eg(a,mod,x,y);
    return (x%mod+mod)%mod;
}
int f_s(int n){//求10^n
    if(n==0)return 1;
    if(n==1)return 10;
    int r=f_s(n/2);
    if(n&1){
        return Mod(Mod(r*r)*10);
    }
    else{
        return Mod(r*r);
    }
}
long long f_s1(int n){//求q(n)
    if(n==1)return 1;
    if(n==2)return 11;
    long long r=f_s1(n/2);
    if(n&1){
        return Mod(Mod(r*Mod(f_s(n/2))+r)*10+1);
    }
    else{
        return Mod(r*Mod(f_s(n/2))+r);
    }
}
long long s_s1(int n){
    int o=0;
    for(int i=0;i<n;i++){
        o=o*10+1;
        o%=mod;
    }
    return o;
}
void solve(){
    int k;
    cin>>k;
    int a,l;
    int suma=0,n=0,o=0,ans;
    for(int i=0;i<k;i++){
        cin>>a>>l;
        n+=l;
        suma+=a*l;
        n%=mod;
        suma%=mod;
    }
    o=f_s1(n);
    n=ny(n);
    ans=n*o;
    ans%=mod;
    ans*=suma;
    ans%=mod;
    cout<<ans<<endl;
    return;
}
signed main(){
    int T;
    cin>>T;
    for(int t=0;t<T;t++){
        solve();
    }
    return 0;
}

最终复杂度 O(T(k+\log n))

完结撒花！