Qiuly

「MtOI2019」小铃的烦恼 概率/期望+线性高斯消元
简单的讲一讲。我们可以钦定某一个魔法属性,使得这个魔法属性是最终的属性。那么其贡献很显然就是该属性变为最终属性的概...
扫描右侧二维码阅读全文
24
2019/08

「MtOI2019」小铃的烦恼 概率/期望+线性高斯消元

简单的讲一讲。

我们可以钦定某一个魔法属性,使得这个魔法属性是最终的属性。

那么其贡献很显然就是该属性变为最终属性的概率$\times$该属性变为最终属性所需要的期望步数

将其依次求出。


概率。

很显然如果当前局面有 $i$ 个当前魔法属性,那么这一次操作有 $\frac{2i(n-i)}{n(n-1)}$ 的概率使得 $i$ 变化,其中 $\frac{i(n-i)}{n(n-1)}$ 的概率使得 $i$ 加 $1$ ,$\frac{i(n-i)}{n(n-1)}$ 的概率使得 $i$ 减 $1$ 。

设 $p_i$ 表示当前有 $i$ 个答案魔法属性时,钦定的魔法属性变为最终答案的概率。

可以得到 $p_i=\frac{p_{i-1}+p_{i+1}}{2}$ ,因为是等差数列,所以可以得到 $p_i=\frac{i}{n}$ 。


期望。

设 $f_i$ 表示当前有 $i$ 个答案魔法属性时,钦定的魔法属性变为最终答案的期望步数。

注意这是条件期望,也就是说转移的时候对于 $f_{i-1}$ 和 $f_{i+1}$ 我们不能给其分配一样的概率,毕竟两个状态到最终状态的概率不一样。

所以转移方程为:

$$f_{i}=\frac{n(n-1)}{2i(n-i)}+\frac{i-1}{2i}f_{i-1}+\frac{i+1}{2i}f_{i+1}$$

这样直接用线性高斯消元即可,复杂度 $O(n)$ 。


代码。

#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
 
const int N=1e4+2;
 
double f[N],a[N],b[N],inv,num,ans;
int n,tot[27];
char s[N];
 
int main() {
    scanf("%s",s+1);
    for(n=1;s[n];++n) ++tot[s[n]-'A'];
    --n,a[1]=1,b[1]=0.5*n;
    for(int i=1;i<=n;++i) for(int j=1;j<=n;++j)
        scanf("%lf",&inv);
    for(int i=2;i<n;++i) {
        inv=0.5/i,num=1.0/(1-(i-1)*inv*a[i-1]);
        a[i]=(i+1)*inv*num;
        b[i]=((i-1)*inv*b[i-1]+n*(n-1)*inv/(n-i))*num;
    }
    for(int i=n-1;i>=1;--i) f[i]=a[i]*f[i+1]+b[i];
    for(int i=0;i<26;++i) ans+=1.0*tot[i]/n*f[tot[i]];
    printf("%.1lf\n",ans);
    return 0;
}
最后修改:2019 年 08 月 24 日 04 : 04 PM

16 条评论

  1. Nickel_Angel

    请问“线性高斯消元”是什么原理QAQ?蒟蒻看不懂大佬的代码QAQ……

    1. Qiuly
      @Nickel_Angel

      就是令一个 $k_i$ 和 $b_i$ 使得 $f_i=k_if_{i+1}+b_i$ ,然后将这个式子带入到 $f_{i-1}$ 中,两边消一消就得到了 $k,b$ 的递推式,这样就可以求出 $f_i$ 了。

      1. Nickel_Angel
        @Qiuly

        感谢dalao QwQ

  2. oldherd

    还有个疑问要麻烦dalao诶。关于$f_i = \frac{n(n-1)}{2i(n-i)}+\frac{i-1}{2i}f_{i-1}+\frac{i+1}{2i}f_{i+1}$是根据条件概率得来的。但为什么不应该是$f_i = \frac{n(n-1)}{2i(n-i)}+\frac{1}{2}p_{i-1}* f_{i-1}+\frac{1}{2}{p_{i+1}}* f_{i+1} = \frac{n(n-1)}{2i(n-i)}+\frac{i-1}{2n}f_{i-1}+\frac{i+1}{2n}f_{i+1}$

    1. Qiuly
      @oldherd

      是这样的,我们考虑的 $p_i$ 是全局的情况,但是现在我们考虑的 $f_i$ 只有两种情况:$f_{i-1}$ 和 $f_{i+1}$ ,所以下面的除数并不为 $2n$ ,我们最终计算的还是两个概率除上两个概率的和,因为我们只会在这两种情况之间选一个。

      1. oldherd
        @Qiuly

        谢谢dalao。似乎有些明白了。您的意思是不是我们定义的$f_i$是在成功的情况下,因此只需要根据两边的成功率分配?

        1. Qiuly
          @oldherd

          毕竟 $f_i$ 以什么概率往 $f_{i-1},f_{i+1}$ 那边走这个和 $n$ 没有任何关系,只需要给 $f_{i-1},f_{i+1}$ 分配概率即可QAQ

    2. buzhibujue
      @oldherd

      同问啊⌇●﹏●⌇

  3. syh

    请问
    pi为什么等于(pi-1 + pi+1)/2 呢 ,然后pi=i/n又是怎样推出来的,求助。

    1. chao
      @syh

      我也没有看懂...
      "因为i的局面到i-1和i+1的局面的概率是相等的"

    2. Qiuly
      @syh

      因为i的局面到i-1和i+1的局面的概率是相等的,然后就是下面的这个柿子将上面的柿子移项即可得到

      1. oldherd
        @Qiuly

        求助ovo。萌新刚接触期望这块。 在$p_i = \frac{p_{i-1}+p_{i+1}}{2}$种的疑问:局面i个钦定元素是有等概率转化为i-1,i+1,但是也有概率不变?为什么不用考虑还有一定概率不变(就是没有转化出去)的情况?

        1. Qiuly
          @oldherd

          是这样的,因为当前我们只需要计算概率,除非是计算期望,否则不变的情况是不用考虑的呀。

          那么剩下的情况就是概率相等了,因为 $i$ 的局面到 $i-1,i+1$ 的局面的概率都是 $\frac{i(n-i)}{n(n-1)}$ ,然后因为这不是计算期望,我们不考虑不变。于是我们就可将这 $2i(n-i)$ 种使得我们局面变化的方案化作所有可选方案,在所有可选方案下,到 $i-1,i+1$ 的概率是 $1:1$ 的,于是可以直接转移了。

          1. oldherd
            @Qiuly

            谢谢dalao

  4. oldherd

    %%%

  5. wsm000

    前排orz。。。

发表评论