题面

$n$ $P$ $k$ 个人是最终唯一的幸存者的概率。

Solution

很有意思的一道题，和一般的朴素概率 DP 不尽相同。

前面的思路和其它题解差不多，主要细说一下最后推式子的步骤。

$n = 1$ $n = 2$ $dp(2, i)$ $2$ $i$ 位的人幸存的概率，不难发现转移：

d p (2, 1) = P \times 0 + (1 - P) \times d p (2, 2)

$1$ $2$ 位置后仍然幸存即为答案。

$dp(2, 1) + dp(2, 2) = 1$ ，所以也可以计算。

$dp(n, i)$ ，不难想到最朴素地：

d p (n, 1) = (1 - P) \times d p (n, n)

\sum_{i = 1}^{n} d p (n, i) = 1

此时我们仔细想一下刚才的过程，不难发现意义就是我们每次只崩首位的人，崩完之后不移动枪，而是将整个圆排列对应旋转。

$dp(n, k)$ $P$ $k \leftarrow k - 1, n \leftarrow n - 1$ $P \times dp(n - 1, k - 1)$ $1 - P$ $k \leftarrow k - 1$ $(1 - P) \times dp(n, k - 1)$ ，于是转移即为：

d p (n, k) = P \times d p (n - 1, k - 1) + (1 - P) \times d p (n, k - 1)

$n$ $n$ $1$ $O(n^4)$ 的，考虑优化。

$P \times dp(n - 1, k - 1)$ $\xi$ ，则有：

d p (n, k) = (1 - P) \times d p (n, k - 1) + ξ

$f(k) = dp(n, k)$ $\xi(k)$ $dp(n - 1, k - 1) \times P \times (1 - P)^{k - 1}$ ，则有：

f (k) = (1 - P)^{k - 1} f (1) + \sum_{i = 1}^{k - 1} ξ (i)

$f(1)$ $f(k)$ $\sum f(k) = 1$ $f(1)$ $O(n)$ $f(k)$ 。

$P = 0$ 的情况，且注意需要滚动数组优化空间。

$O(n^2)$ $O(n)$ 。

Code


xxxxxxxxxx
65
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define EPS (1e-10)
24

25
template < typename T = int >
26
inline T read(void);
27

28
ld P;
29
int N, K;
30
ld dp[2][11000];
31

32
int main(){
33
    scanf("%Lf", &P), N = read(), K = read();
34
    if(P < EPS)printf("%.10Lf\n", N == 1 ? (ld)1 : (ld)0), exit(0);
35
    dp[1][1] = 1.0;
36
    bool cur(false);
37
    for(int i = 2; i <= N; ++i){
38
        ld K(1.0), B(0.0), base1(1.0), base2(0.0);
39
        for(int j = 2; j <= i; ++j)
40
            base1 *= (1 - P), base2 = base2 * (1 - P) + P * dp[cur ^ 1][j - 1],
41
            K += base1, B += base2;
42
        dp[cur][1] = (1 - B) / K;
43
        for(int j = 2; j <= i; ++j)
44
            dp[cur][j] = (1 - P) * dp[cur][j - 1] + P * dp[cur ^ 1][j - 1];
45
        cur ^= 1;
46
    }printf("%.10Lf\n", dp[cur ^ 1][K]);
47
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
48
    return 0;
49
}
50

51
template < typename T >
52
inline T read(void){
53
    T ret(0);
54
    int flag(1);
55
    char c = getchar();
56
    while(c != '-' && !isdigit(c))c = getchar();
57
    if(c == '-')flag = -1, c = getchar();
58
    while(isdigit(c)){
59
        ret *= 10;
60
        ret += int(c - '0');
61
        c = getchar();
62
    }
63
    ret *= flag;
64
    return ret;
65
}

UPD

update-2023_02_25 初稿

LG-P5249 [LnOI2019]加特林轮盘赌 Solution

更好的阅读体验戳此进入

题面

Solution

Code

UPD