HDU4652 Dice [期望]

Author Avatar
空気浮遊 2019年02月16日
  • 在其它设备中阅读本文章
  • 分享到 Facebook
  • 分享到 Telegram
  • 分享到 Twitter
  • 分享到微博

Solution

第一问考虑状态 $E(x)$ 为已经连续拿了 $x$ 个相同骰子的期望。

则有方程 $E(x)=\frac{1}{m}E(x+1)+\frac{m-1}{m}E(1)+1$

发现方程只跟 $E(1)$ 和常数项有关,且有 $E(1)=E(0)+1$,则我们可以由前向后递推得到方程解得 $E(1)$。

第二问类似地有:
$$E(x)=1+\frac{m-x}{m}E(x+1)+\frac{x}{m}\frac{1}{x}\sum \limits_{i=1}^xE(i)$$

同样的推到最后 $E(n)=0$ 时解方程即可。

Code

// Code by ajcxsu
// Problem: dice

#include<bits/stdc++.h>
using namespace std;

const int N=1e6+10;
struct Node {
    double a, b;
    Node operator * (double x) { return {a*x, b*x}; }
    Node operator - (Node x) { return {a-x.a, b-x.b}; }
    Node operator + (Node x) { return {a+x.a, b+x.b}; }
} f[N], s[N];

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.setf(ios::fixed), cout<<setprecision(7);
    int t;
    cin>>t;
    while(t--) {
        int o, n;
        double m;
        cin>>o>>m>>n;
        if(m==1) { cout<<n<<endl; continue; }
        s[1]=f[1]={1, 0};
        if(!o)
            for(int i=2;i<=n;i++) f[i]=f[i-1]*m-(Node){m-1, m};
        else
            for(int i=2;i<=n;i++) {
                f[i]=f[i-1]*((m-1)/(m-i+1))-s[i-2]*(1/(m-i+1))-(Node){0, m/(m-i+1)};
                s[i]=f[i]+s[i-1];
            }
        cout<<(-f[n].b/f[n].a)+1.0<<endl;
    }
    return 0;
}

本文链接:https://pst.iorinn.moe/archives/sol-hdu-4652.html
许可: https://pst.iorinn.moe/license.html
若无特别说明,博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆

      新篇
旧篇      
    • fingerprint Login
  • home 主页
  • inbox 归档
    • December 2024 1
    • August 2024 1
    • June 2024 1
    • April 2024 3
    • March 2024 1
    • February 2024 2
    • January 2024 1
    • November 2023 1
    • August 2023 1
    • May 2023 1
    • February 2023 2
    • January 2023 2
    • July 2022 1
    • June 2022 1
    • April 2022 1
    • March 2022 1
    • February 2022 2
    • December 2021 1
    • November 2021 1
    • August 2021 3
    • July 2021 3
    • April 2021 2
    • March 2021 1
    • February 2021 4
    • January 2021 2
    • December 2020 1
    • November 2020 1
    • October 2020 3
    • September 2020 1
    • August 2020 1
    • July 2020 1
    • March 2020 1
    • December 2019 1
    • September 2019 1
    • July 2019 1
    • April 2019 2
    • March 2019 13
    • February 2019 15
    • January 2019 11
    • December 2018 3
    • November 2018 6
    • October 2018 28
    • September 2018 32
    • August 2018 19
    • July 2018 13
    • June 2018 27
    • May 2018 11
    • April 2018 12
    • March 2018 19
    • February 2018 8
    • January 2018 7
    • December 2017 2
    • November 2017 2
  • apps 分类
    • 笔记
    • 题解
    • 杂文
    • 技术
    • 游戏
    • 小说
  • 留言板
  • 关于
  • 友链
  • 文章总数 282
主题 - Material i
expand_less
Copyright © 2025 雪屋
Float in air.
Powered by Typecho
Theme - Material