期望 get！

· · 个人记录

入门：

传送门

代码及其简单，但作为刚学期望的蒟蒻，这个题真的是**

由于（愚蠢的） gx 把答案抄错了一位，所以，这个方程的第 i 道题必与第 i-1道有关

如果我们看第 i 道题与第 i-1 道题，有这么两种可能：

1、a[i]>a[i-1]:

那么第 i 题答案在 i-1 的选项中的概率为 a[i-1]/a[i]

而选出正确答案的概率为 1/a[i-1]

两式相乘，得：1/a[i]

2、a[i]<a[i-1]:

那么第 i-1 题所填的选项也在第 i 题中的概率为 a[i]/a[i-1]

而第 i 题的正确概率为 1/a[i]

综合一下得：1/a[i-1]

所以总的方程式为：1/max(a[i],a[i-1])

int n,A,B,C;
int a[MAXN];
double ans;

int main(void)
{
                /*数据生成器，不用多管*/
//******************************************************
    scanf("%d%d%d%d%d",&n,&A,&B,&C,a+1);
    for(int i=2;i<=n;i++)
        a[i] = ((long long)a[i-1]*A+B) % 100000001;
    for(int i=1;i<=n;i++)
        a[i] = a[i]%C+1;
//******************************************************
    a[0] = a[n];
    for(int i=1;i<=n;i++)
        ans += 1/(double)max(a[i],a[i-1]);
    printf("%.3lf",ans);
    return 0;
}

基础：

传送门

先看前 7 次释放魔法，每次都不同的概率为：

\frac{a_1}{n} \times \frac{a_2}{n-1} \times \frac{a_3}{n-2} \times \frac{a_4}{n-3} \times \frac{a_5}{n-4} \times \frac{a_6}{n-5} \times \frac{a_7}{n-6}

注意，这时分子的排列顺序是可以随意换的，所以一共有 7! 排列，

那么，在第 7 次能放帕琪七重奏的概率为：

7! \times \frac{a_1}{n} \times \frac{a_2}{n-1} \times \frac{a_3}{n-2} \times \frac{a_4}{n-3} \times \frac{a_5}{n-4} \times \frac{a_6}{n-5} \times \frac{a_7}{n-6}

接下来再看第 8 次，要想在第 8 次也放帕琪七重奏，就需要 2 ~ 8 次使用的晶体各不相同，也就是第 8 次要与第 1 次相同，就有如下：

\frac{a_1}{n} \times \frac{a_2}{n-1} \times \frac{a_3}{n-2} \times \frac{a_4}{n-3} \times \frac{a_5}{n-4} \times \frac{a_6}{n-5} \times \frac{a_7}{n-6} \times \frac{a_1-1}{n-7}

不过，由于第 1 项可以用 1 ~ 7 中的任意一种，所以第 8 项一共有 7 种可能，上式只是其中一种。这 7 种由于没有互相限制，我们来一手加法原理，然后就发现又回到了第一个方程：

\frac{a_1}{n} \times \frac{a_2}{n-1} \times \frac{a_3}{n-2} \times \frac{a_4}{n-3} \times \frac{a_5}{n-4} \times \frac{a_6}{n-5} \times \frac{a_7}{n-6}

也就是说，对于释放第 8 个魔法以及之后的魔法时能触发帕琪七重奏的概率仍是上式，所以从释放第七个魔法开始到第 n 个，一共可以有 n-6 次机会触发帕琪七重奏，每次的概率都是上式，所以总答案就要乘以 n-6 ：

7! \times \frac{a_1}{n} \times \frac{a_2}{n-1} \times \frac{a_3}{n-2} \times \frac{a_4}{n-3} \times \frac{a_5}{n-4} \times \frac{a_6}{n-5} \times a_7 
signed main(void)
{
    for(int i=1;i<=7;i++)
    {
        cin >> a[i];
        n += a[i];
    }
    printf("%.3lf",5040*a[1]/n*a[2]/(n-1)*a[3]/(n-2)*a[4]/(n-3)*a[5]/(n-4)*a[6]/(n-5)*a[7]);
    return 0;
}

经典：

传送门

期望的经典题目。

至今没有明白公式的推导过程，希望有知道原理的大佬下方评论

下面的话摘自 LDL 语录：

“离散型的期望可以看成是概率的倒数。”

所以，设已经收集了 i 个人，那么抽到一个没收集过的人的概率为 \tfrac{n-i}{n} ，那么期望就是 \tfrac{n}{n-i} ，所以总的期望就是：

n \times (\tfrac{1}{1} \times \tfrac{1}{2} \times \tfrac{1}{3} \times \cdots \times \tfrac{1}{n})

个人建议：这道题其实是考的 gcd 和模拟（看那变态的输出要求），如果推出了公式建议直接找题解水过去。 

#define int long long
int N,ansfz,ansfm;
int fm,fz;

int gcd(int a,int b) {return b ? gcd(b,a%b) : a;}

void OutPut()
{
    if(ansfm == 1)
    {
        cout << ansfz;
        return;
    }
    int x = ansfz/ansfm;
    int temp = x,num = 0;
    ansfz %= ansfm;
    while(temp)
    {
        num++;
        temp /= 10;
    }
    for(int i=1;i<=num;i++) cout << " ";
    cout << ansfz << endl;
    if(x) cout << x;
    temp = ansfm;
    while(temp)
    {
        cout << "-";
        temp /= 10;
    }
    cout << endl;
    for(int i=1;i<=num;i++) cout << " ";
    cout << ansfm << endl;
}

signed main()
{
    cin >> N;
    ansfz = N;
    ansfm = 1;
    for(int i=2;i<=N;i++)
    {
        fz = N;
        fm = i;
        int g = gcd(fm,ansfm);
        ansfz = ansfz*(fm/g)+fz*(ansfm/g);
        ansfm *= (fm/g);
        g = gcd(ansfz,ansfm);
        ansfz /= g;
        ansfm /= g;
    }
    OutPut();
    return 0;
}