数学题(期望+分数计算)-UVA 10288-Coupons

た入场券 2022-05-15 23:30 162阅读 0赞

*  # 数学题(期望+分数计算)-UVA 10288-Coupons #

--------------------

*  ## 题目链接：[10288 - Coupons][] ##
 *  ## 思路： ##

**题目大意是有n种奖，每种奖在一张彩票中获得的几率相同，问要集齐n种奖，需要买的彩票数量的期望，用整数加分式(要求最简分式）表示**

**期望是线性的，所以采用分治法的思想求整体期望**

**设Y为集齐n种奖需要买的彩票数量**

**设 ![Y\_\{k\}][Y_k] 为已获得 k 种奖后，想收集到第 k+1 种奖需要买的彩票数量**

**可得![Y=Y\_\{0\}+Y\_\{1\}+Y\_\{2\}+...+Y\_\{n-1\}][Y_Y_0_Y_1_Y_2_..._Y_n-1]**

**由期望的线性：![E(Y)=E(Y\_\{0\}+Y\_\{1\}+Y\_\{2\}+...+Y\_\{n-1\})=E(Y\_\{0\})+E(Y\_\{1\})+E(Y\_\{2\})...+E(Y\_\{n-1\})][E_Y_E_Y_0_Y_1_Y_2_..._Y_n-1_E_Y_0_E_Y_1_E_Y_2_..._E_Y_n-1]**

**因为获得k种奖后，再想获得第k+1种奖的概率为 (n-k)/n ，设对立面不能获得第k+1种奖的概率为 p=k/n**

**能否获得是互相对立的（条件概率），所以要获得第k+1奖所需买的彩票数可能为 1~m（*m为无穷大，可能运气差一直开不到*）**

**得 收集到第k+1张彩票需要买 t 张彩票的概率为 ![P\_\{t\}=p^\{t-1\}\*(1-p)][P_t_p_t-1_1-p]**

**所以 ![Y\_\{k\}][Y_k] 的期望为：![E(Y\_\{k\})=\\sum\_\{n\}^\{t=1\}t\*P\_\{t\}=(1-p)(1+2p+3p^\{2\}+...+mp^\{m-1\})][E_Y_k_sum_n_t_1_t_P_t_1-p_1_2p_3p_2_..._mp_m-1]**

**利用数列错位相减法求得 ![E(Y\_\{k\})=\\frac\{1-p^\{m-1\}\}\{1-p\}-mp^\{m\}][E_Y_k_frac_1-p_m-1_1-p_-mp_m]**

**因为m为无穷大，取极限后 ![E(Y\_\{k\})=\\frac\{1\}\{1-p\}=\\frac\{1\}\{1-\\frac\{k\}\{n\}\}=\\frac\{n\}\{n-k\}][E_Y_k_frac_1_1-p_frac_1_1-_frac_k_n_frac_n_n-k]**

**求到最后居然发现 ![E(Y\_\{k\})=\\frac\{1\}\{1-p\}][E_Y_k_frac_1_1-p]，也就是获得第k+1种奖的概率的倒数，感觉还是记住公式吧~条件概率的公式**

**最后对各部分期望求和 ![E(Y)=\\frac\{n\}\{n\}+\\frac\{n\}\{n-1\}+\\frac\{n\}\{n-2\}+...+\\frac\{n\}\{1\}=\\sum\_\{i=0\}^\{n\}\\frac\{1\}\{n-i\} or \\sum\_\{i=1\}^\{n\}\\frac\{1\}\{i\}][E_Y_frac_n_n_frac_n_n-1_frac_n_n-2_..._frac_n_1_sum_i_0_n_frac_1_n-i_ or _sum_i_1_n_frac_1_i]**

**我是用左边的累加式计算，两个累加式都一样啦**

然后就是分数计算，别看33小，不用long long分分钟WA到自闭，我怕溢出，**每进行一次分数相加就检查然后取出整数加约分**

*  ## 代码： ##

#include <iostream>
    
    using namespace std;
    
    long long gcd(long long a,long long b) //最大公约数
    {
        return b==0? a : gcd(b,a%b);
    }
    
    long long lcd(long long a,long long b)  //最小公倍数
    {
        return (a*b)/gcd(a,b);
    }
    
    int main()
    {
        int n;
        while(cin>>n)
        {
            int Inter_num=0;
            long long Fenzi,Fenmu;
            long long Res_z=0,Res_m=0;
            for(int i=0;i<n;i++)
            {
                Inter_num+=n/(n-i);   //整数部分直接加上
                Fenzi=n-(n/(n-i))*(n-i);  //分子
                Fenmu=n-i;    //分母
                if(Fenzi!=0)    //有分数部分进行分数相加
                {
                    if(Res_z==0)   //初始化
                    {
                        Res_m+=Fenmu;
                        Res_z+=Fenzi;
                    }
                    else
                    {
                        long long new_mu;
                        if(Fenmu>Res_m)    //通分求分母
                            new_mu=lcd(Fenmu,Res_m);  
                        else
                            new_mu=lcd(Res_m,Fenmu);
                        Res_z=(new_mu/Res_m)*Res_z+(new_mu/Fenmu)*Fenzi;  //相加后分子
                        Res_m=new_mu;    //新分母
                        if(Res_z>Res_m)    //提取整数部分
                        {
                            Inter_num+=Res_z/Res_m;
                            Res_z-=(Res_z/Res_m)*Res_m;
                        }
                       
                        //进行约分
                        new_mu=gcd(Res_m,Res_z);
                        if(new_mu!=1)
                        {
                            Res_z/=new_mu;
                            Res_m/=new_mu;
                        }
                    }
                }
            }
            if(Res_z==0)
                cout<<Inter_num<<endl;  //只有整数直接输出
            else   //打印分数，三行，用空格控制格式
            {
                int bit=0;
                long long Temp=Inter_num;
                while(Temp)
                {
                    bit++;
                    Temp/=10;
                }
                for(int i=0;i<=bit;i++)
                    cout<<" ";
                cout<<Res_z<<endl;
                cout<<Inter_num<<" ";
                Temp=Res_m;
                int bit1=0;
                while(Temp)
                {
                    bit1++;
                    Temp/=10;
                }
                for(int i=0;i<bit1;i++)
                    cout<<"-";
                cout<<endl;
                for(int i=0;i<=bit;i++)
                    cout<<" ";
                cout<<Res_m<<endl;
            }
    
        }
        return 0;
    }

*  ## 我想BB： ##

我想低调说下，我真的是全网求期望最走心的人~

[10288 - Coupons]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1229
[Y_k]: https://private.codecogs.com/gif.latex?%5Cinline%20%5Cdpi%7B120%7D%20Y_%7Bk%7D
[Y_Y_0_Y_1_Y_2_..._Y_n-1]: https://private.codecogs.com/gif.latex?%5Cinline%20Y%3DY_%7B0%7D&plus;Y_%7B1%7D&plus;Y_%7B2%7D&plus;...&plus;Y_%7Bn-1%7D
[E_Y_E_Y_0_Y_1_Y_2_..._Y_n-1_E_Y_0_E_Y_1_E_Y_2_..._E_Y_n-1]: https://private.codecogs.com/gif.latex?%5Cinline%20E%28Y%29%3DE%28Y_%7B0%7D&plus;Y_%7B1%7D&plus;Y_%7B2%7D&plus;...&plus;Y_%7Bn-1%7D%29%3DE%28Y_%7B0%7D%29&plus;E%28Y_%7B1%7D%29&plus;E%28Y_%7B2%7D%29...&plus;E%28Y_%7Bn-1%7D%29
[P_t_p_t-1_1-p]: https://private.codecogs.com/gif.latex?%5Cinline%20%5Cdpi%7B120%7D%20P_%7Bt%7D%3Dp%5E%7Bt-1%7D*%281-p%29
[E_Y_k_sum_n_t_1_t_P_t_1-p_1_2p_3p_2_..._mp_m-1]: https://private.codecogs.com/gif.latex?%5Cinline%20E%28Y_%7Bk%7D%29%3D%5Csum_%7Bn%7D%5E%7Bt%3D1%7Dt*P_%7Bt%7D%3D%281-p%29%281&plus;2p&plus;3p%5E%7B2%7D&plus;...&plus;mp%5E%7Bm-1%7D%29
[E_Y_k_frac_1-p_m-1_1-p_-mp_m]: https://private.codecogs.com/gif.latex?%5Cinline%20%5Cdpi%7B120%7D%20E%28Y_%7Bk%7D%29%3D%5Cfrac%7B1-p%5E%7Bm-1%7D%7D%7B1-p%7D-mp%5E%7Bm%7D
[E_Y_k_frac_1_1-p_frac_1_1-_frac_k_n_frac_n_n-k]: https://private.codecogs.com/gif.latex?%5Cinline%20%5Cdpi%7B120%7D%20E%28Y_%7Bk%7D%29%3D%5Cfrac%7B1%7D%7B1-p%7D%3D%5Cfrac%7B1%7D%7B1-%5Cfrac%7Bk%7D%7Bn%7D%7D%3D%5Cfrac%7Bn%7D%7Bn-k%7D
[E_Y_k_frac_1_1-p]: https://private.codecogs.com/gif.latex?%5Cinline%20%5Cdpi%7B120%7D%20E%28Y_%7Bk%7D%29%3D%5Cfrac%7B1%7D%7B1-p%7D
[E_Y_frac_n_n_frac_n_n-1_frac_n_n-2_..._frac_n_1_sum_i_0_n_frac_1_n-i_ or _sum_i_1_n_frac_1_i]: https://private.codecogs.com/gif.latex?E%28Y%29%3D%5Cfrac%7Bn%7D%7Bn%7D&plus;%5Cfrac%7Bn%7D%7Bn-1%7D&plus;%5Cfrac%7Bn%7D%7Bn-2%7D&plus;...&plus;%5Cfrac%7Bn%7D%7B1%7D%3D%5Csum_%7Bi%3D0%7D%5E%7Bn%7D%5Cfrac%7B1%7D%7Bn-i%7D%20or%20%5Csum_%7Bi%3D1%7D%5E%7Bn%7D%5Cfrac%7B1%7D%7Bi%7D