Implication

topic link

Give you a dice with n sides, you can roll up to k times, you can stop rolling the dice at any time, and use the last result as your score, the probability of each side of the dice appearing is equal, let you ask forWhat is the expectation to score at most k shots.

Analysis

Let's take a 20-sided dice roll up to 3 times as an example:

Only one throw: the probability of each side is \frac{1}{20}, multiplying the score of each case, you can get: \frac{1}{20} * \sum^{20}_{i= 1}{i} = 10.5

At most two throws: The expectation of one throw is 10.5 points, so the second throw is only performed if the first score is lower than 10.5, so it is divided into one throw and two throws. The expectation of one throw is:\frac{1}{20} * \sum_{i=11}^{20}i, the expectation of two throws can be regarded as the premise that the result of the first throw is 1-10, another throw, i.e. the probability of the first throw being 1-10 times the expectation of only one throw.In summary, the formula is: \frac{1}{20} * \sum_{i=11}^{20}i+\frac{10}{20} * 10.5 = 13

Three throws at most: The expectation of throwing twice is 13, then if the result of the first throw is 1-13, then throwing twice is definitely better, so it can be divided into two situations: the result of the first throwis 14-20, then as long as you vote once, the expectation is: \frac{1}{20} * \sum_{i=14}^{20}i; the first result is 1-13, then you need to continue throwing, which can be regarded as the expectation of throwing at most two times on the basis of the first throwing result of 1-13, namely: \frac{13}{20} * 13

It can be found that each time the result is derived from the previous step, and a recursive relationship can be obtained, then to find the n dice, roll k times as long asIt can be pushed from 1 times to k times. Since the interval sum is used, it can be preprocessed with the prefix sum, and the code implementation is simple.

code

#include #define LL long longusing namespace std;const int maxn = 1e5+10;const int inf = 0x3f3f3f3f;const double PI = acos(-1.0);typedef pair PII;typedef pair PLL;double s[110];LL n, k;int main() {scanf("%lld %lld", &n, &k);for (LL i = 1; i <= n; i++) {s[i] = s[i - 1] + i;}double t = s[n] / n;for (LL i = 2; i <= k; i++) {LLpos = (LL)t;t = (s[n] - s[pos]) / n + (pos)*t / n;}printf("%.8lf\n", t);return 0;}