qduoj-一个数变成0的概率有多少？（简单的概率dp）

题目链接：https://qduoj.com/problem/822

Description

 

给定一个数a0, 并给出定义:序列a1,a2,a3......

1.从闭区间[0,a0]中等概率随机选择一个整数k0,令a1=a0-k0

2.得到随机数a1后，再从闭区间[0,a1]中等概率随机选择一个整数k1,令a2=a1-k1

3.一般地，得到随机数ai后，再从闭区间[0,ai]中等概率随机选择一个整数ki,令a(i+1) = ai- ki

问经过n步后，an==0的概率是多少呢？

Input

 

输入两个正整数n,a0

(1<=n,a0<=100)

Output

 

输出概率，小数点后四舍五入保留5位小数

Sample Input 1

3 3

Sample Output 1

0.72049

思路：二维数组d[i][j]表示第i次操作后ai==j的概率。具体见代码。

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <map> #include <set> #include <stack> #include <queue> #include <vector> #include <string> #define cla(a, sum) memset(a, sum, sizeof(a)) #define rap(i, m, n) for(int i=m; i<=n; i++) #define rep(i, m, n) for(int i=m; i>=n; i--) #define bug printf("???\n") using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll> P; const int Inf = 0x3f3f3f3f; const double eps = 1e-8; const int maxn = 3e4; template <typename T> void read(T &x){ x = 0; int f = 1; char ch = getchar(); while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();} while (isdigit(ch)) {x = x * 10 + ch - '0'; ch = getchar();} x *= f; } int n,a; double d[105][105]={0}; int main() { read(n);read(a); rap(i,0,a){ d[1][i]=1.0/(a+1); } rap(i,2,n){//次数 for(int j=0;j<=a;j++){//区间长度 for(int k=0;k<=j;k++){ d[i][k]+=d[i-1][j]/(j+1); } } } printf("%.5lf\n",d[n][0]); return 0; }