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 许可协议 进行许可☆