题解 P5081 【Tweetuzki 爱取球】

· · 题解

题解思路：正难则反

我们发现，因为该期望的概率数列是个不收敛数列，所以要想顺着题目的思路去推出期望几乎是不可能的，因此我们要另辟蹊径

引理：

求证：

假设对于一件事A，我们每一次做A时的成功率是P，如果本次不成功就继续做，最终期望\dfrac{1}{p}次做成

证明：

对于这个问题，我们显然不能正向去想，我们可以利用一个叫做递归公式的东西：我们设期望k次做成A ，则有：

k=1+p*0+(1-p)*k

其中1表示第一次做A，如果成功了就再做0次，期望次数为p*0；如果不成功就再做k次，期望为(1-p)*k

通过移项，我们得到

k=\dfrac {1}{p}

引理证毕

正文：

我们先来思考一个问题：从n个球里取出1个球的概率是多少

答案很简单，显然是1，由引理得，取出1个球成功的期望次数为k_1=\dfrac{1}{p}=\dfrac{1}{1}=1

那从n个球中取出其他n-1个球中的一个球的概率呢？其实也很好算，就是\dfrac{n-1}{n}，那成功的期望次数就是k_2=\dfrac{1}{p}=\dfrac{n-1}{n}

以此类推……………………

则取遍这n个球的总期望次数为：k_{sum}=k_1+k_2+\text{…}+k_n=\dfrac{n}{n}+\dfrac{n}{n-1}+\text{…}+\dfrac{n}{1}=n*\sum\limits_{i=1}^{n-1}\dfrac{1}{n-i}

所以最终这个题就是求个逆元和乘n就完事了

附加证明：线性筛逆元

我们知道，对于任意一个数p，都有p=a*b+c（a,b,c为任意整数）

则对于式子p\equiv0\text{(mod p)}

我们有a*b+c\equiv0\text{(mod p)}

把c挪到右边：a*b\equiv-c\text{(mod p)}

两边同时乘c的逆元c^{-1}：a*b*c^{-1}\equiv-1\text{(mod p)}

两边再同时乘b的逆元b^{-1}：a*c^{-1}\equiv-b^{-1}\text{(mod p)}

即可化为b^{-1}\equiv-a*c^{-1}\text{(mod p)}

同时，我们知道，在c++里，int类的除法都是自动向下取整的。所以我们可以得到：对于数p=a*b+c，有a=\dfrac{p}{b}、c=p\%b（我们要求的是b的逆元，p是模数）。我们设inv[i]为i的逆元，则有递推式：

inv[i]=(1ll*(p-\dfrac{p}{i})*inv[p\%i])\%p

证毕

以下是code：

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const int p=20040313;
ll inv[10000010],sum,n;
int main()
{
    scanf("%lld",&n);
    inv[1]=1;sum+=1;
    for(int i=2;i<=n;i++)//简短有力
    inv[i]=(1ll*(p-p/i)*inv[p%i])%p,sum=(sum+inv[i])%p;
    printf("%lld",n*sum%p);
    return 0;
}