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

作者: wjyyy 分类: DP,gcd/lcm,函数,数列,数学,概率期望,解题报告,递推 发布时间: 2018-07-27 15:13

点击量:118

 

    推公式的一道题。

 

题目描述

“……在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;
}

说点什么

avatar
  Subscribe  
提醒
/* */