洛谷 P1291 [SHOI2002]百事世界杯之旅 题解【概率期望】【数列】【递推】/【DP】【gcd/lcm】

点击量：209

    推公式的一道题。

目录

题目描述

“……在2002年6月之前购买的百事任何饮料的瓶盖上都会有一个百事球星的名字。只要凑齐所有百事球星的名字，就可参加百事世界杯之旅的抽奖活动，获得球星背包，随声听，更克赴日韩观看世界杯。还不赶快行动！”

 

你关上电视，心想：假设有n个不同的球星名字，每个名字出现的概率相同，平均需要买几瓶饮料才能凑齐所有的名字呢？

 

输入输出格式

输入格式：

整数n（2≤n≤33），表示不同球星名字的个数。

 

输出格式：

输出凑齐所有的名字平均需要买的饮料瓶数。如果是一个整数，则直接输出，否则应该直接按照分数格式输出，例如五又二十分之三应该输出为：

 3
5--
 20

第一行是分数部分的分子，第二行首先是整数部分，然后是由减号组成的分数线，第三行是分母。减号的个数应等于分母的为数。分子和分母的首位都与第一个减号对齐。

 

分数必须是不可约的。

 

输入输出样例

输入样例#1：

2

输出样例#1：

3

题解 of 递推：

    我们考虑这么一个事情：假设当前我们已经有了$ k$个球星名字，一共有n个球星，那么我们当前一次性获得一个新球星的概率为$ \frac{n-k}n$，没有获得新球星的概率为$ \frac kn$。如果没有获得新球星我们就要买第二瓶、第三瓶……去买第二瓶的概率为$ \frac kn$，也就是如果我买到第一瓶中了，我就不会去针对这些个球星买第二瓶。如果我的运气很差很差很差很差（营销策略），一直买不到那n-k个球星，去买第p瓶且中奖的概率为$ (\frac kn)^{p-1}\times \frac{n-k}n$，因此如果我们把这些概率变为期望求和，那么买第p瓶的期望值就用p去乘上概率。

    这样一来我们如果已经有了$ k$个球星那么期望得到$ k+1$个球星的期望值就是

$ S_p=1\times (\frac kn)^0\times \frac{n-k}n +2\times (\frac kn)^1\times \frac{n-k}n +\cdots +p\times (\frac kn) ^{p-1}\times \frac{n-k}n$

    可以看出这是一个差比数列，差比数列求和要用到错位相减法，先把原式乘上一个$ \frac kn$，拿原式去减，减掉以后变成

$ \frac{n-k}n\times S_p=\frac{n-k}n(\sum\limits_{i=0}^{p-1}(\frac kn)^i-i\times (\frac kn)^{i+1})$

    约掉两侧的$ \frac{n-k}n$就变成了

$ S_p=\sum\limits_{i=0}^{p-1}((\frac kn)^i)-p\times (\frac kn)^{p+1}$

    因为我们无法预见自己的运气有多背，那么我们对上式取极限，当一个小于1的数的指数很大时，它就会趋近于0，$ S_p$的极限也就是

$ \lim\limits_{p\rightarrow \infty}S_p=\sum\limits_{i=0}^{p-1}(\frac kn)^i$

    转化为等比数列求和，就得到了

$ \lim\limits_{p\rightarrow \infty}S_p=\frac{1-(\frac kn)^p}{1-\frac kn}=\frac 1{1-\frac kn}=\frac n{n-k}$

    也就是首项为1的一个等比数列前p项和。

    综上所述，当我们手上有$ k$个球星的名字，并且我们想要转移为$ k+1$个球星，就期望需要$ \frac n{n-k}$次。这样一来，这个递推公式就写出来了，就是

$ f(i)=f(i-1)+\frac n{n-i},f(n)=\sum\limits_{i=0}^{n-1}\frac n{n-k}$

    最后写成带分数的形式要注意’-‘要和分母对齐而不是分子。并注意取gcd来约分，记得开long long。

题解 of 期望DP：

    既然是个期望题，它一定可以用期望DP来做。我们用$ f[i]$表示获取$ i$个球星的期望次数是多少。那么我们有两种情况，一种是从上一个状态获取一张新的球星转移过来，概率为$ \frac{n-(i-1)}n$。而也有可能本来就在$ f[i]$处，结果又抽中了已经有的球星。这个的概率为$ \frac in$，不过做期望题有一个前提就是所有事件发生的概率加起来之和等于1。而这两个加起来并不等于1，我们就要考虑把DP改一改。

    因为$ f[i]$表示的是拿到$ i$个球星的期望次数是多少，而我们知道，一旦拿到第$ i$个，这一阶段就结束了，因为我们的目的已经达成了。所以在上面的第二个概率中，我们只用管抽到前$ i-1$个的概率，因此分子应改为$ i-1$。

    这样一来，状态转移方程就是$ f[i]=f[i-1]\times \frac{n-(i-1)}n+f[i]\times \frac{i-1}n$，我们把$ f[i]$移项，就可以求出$ f[i]$由$ f[i-1]$转移来的方程。不过可以发现，这个方程和上面的递推公式没有什么不同，它们的本质是一样的。因此做法相同。

Code：

#include<cstdio>
#include<cstring>
#include<cmath>
long long gcd(long long x,long long y)
{
    if(x%y==0)
        return y;
    return gcd(y,x%y);
}
long long lcm=1;
int main()
{
    int n;
    scanf("%d",&n);
    for(long long i=1;i<=n;i++)
        lcm=lcm*i/gcd(lcm,i);
    long long up=0;
    for(long long i=1;i<=n;i++)
        up+=lcm/i;
    up*=n;
    long long GCD=gcd(up,lcm);
    up/=GCD;
    lcm/=GCD;
    long long INt=up/lcm;//整数部分
    if(up%lcm==0)
    {
        printf("%lld\n",INt);
        return 0;
    }
    for(long long i=1;i<=log10(INt)+1;i++)
        printf(" ");
    printf("%lld\n",up%lcm);
    printf("%lld",INt);
    for(int i=1;i<=log10(lcm)+1;i++)
        printf("-");
    puts("");
    for(int i=1;i<=log10(INt)+1;i++)
        printf(" ");
    printf("%lld\n",lcm);
    return 0;
}