自动搬运

查看原文

来自洛谷，原作者为

	Protons 消灭[数据删除]暴政，世界属于[数据删除]

搬运于2025-08-24 22:06:57，当前版本为作者最后更新于2019-11-09 17:43:22，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题解思路：正难则反

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

引理：

求证：

假设对于一件事$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;
}