img

概率dp

概率dp,一般来说，我们将dp数组存放的数据定义为到达此状态的概率，那么我们初值设置就是所有初始状态概率为1，最终答案就是终末状态dp值了。

我们在进行状态转移时，是从初始状态向终末状态顺推，转移方程中大致思路是按照当前状态去往不同状态的位置概率转移更新DP，且大部分是加法。

期望dp

用于求解期望的DP。这类问题一般将dp[数组]存放的数据定义为到达终态还需要的期望值。那么初值设置就是终末状态期望为0，答案就是初始状态的dp值了。

我们在进行状态转移时，一般是从终末状态逆推到起始状态，转移方程大致思路是找到当前状态所有可以转移到的状态，将它们的期望依概率相加即可。

练习

A - Scout YYF I

YYF is a couragous scout. Now he is on a dangerous mission which is to penetrate into the enemy's base. After overcoming a series difficulties, YYF is now at the start of enemy's famous "mine road". This is a very long road, on which there are numbers of mines. At first, YYF is at step one. For each step after that, YYF will walk one step with a probability of p, or jump two step with a probality of 1-p. Here is the task, given the place of each mine, please calculate the probality that YYF can go through the "mine road" safely.

Input

The input contains many test cases ended with EOF. Each test case contains two lines. The First line of each test case is N (1 ≤ N ≤ 10) and p (0.25 ≤ p ≤ 0.75) seperated by a single blank, standing for the number of mines and the probability to walk one step. The Second line of each test case is N integer standing for the place of N mines. Each integer is in the range of [1, 100000000].

Output

For each test case, output the probabilty in a single line with the precision to 7 digits after the decimal point.

Sample

Inputcopy Outputcopy
1 0.5 2 2 0.5 2 4 0.5000000 0.2500000

本题递推式非常容易

1
dp[i]=dp[i-1]*p+dp[i-2]*(1-p)

但是直接这样子时空都不会满足

因此考虑矩阵加速递推

1
2
dp[i]  =p  1-p   dp[i-1]
 dp[i-1]=1   0    dp[i-2]

于是重新进行定义：

1
dp[i]=dp[i-1]*(1-p(这里是走到dp[i]的概率))

需要递推中间部分

递推a[i]-a[i-1]+1次

矩阵快速幂方面就不解释了

和最普通的快速幂其实差距不大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
// dp[i]=dp[i-1]*p+dp[i-2]*(1-p)
// 和斐波那契很像
// 可以考虑加速
// dp[i]  =p  1-p   dp[i-1]
// dp[i-1]=1   0    dp[i-2]
// 正确性显然
// 应该是这样子
// dp[i]=dp[i-1]*(1-p(这里是走到dp[i]的概率，所谓递推来自于此))
#include<stdio.h>
#include <iostream>
#include<algorithm>
#include<string.h>
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
using namespace std;
const int N = 1e6 + 10;
int a[N];
double dp[N];
double p;
int n;
struct matrix
{
    double b[2][2];
};
matrix chenfa(matrix a, matrix b)
{
    matrix ans;
    memset(ans.b, 0, sizeof ans.b);
    rep(i, 0, 1)
    {
        rep(j, 0, 1)
        {
            rep(k, 0, 1)
            {
                ans.b[i][j] += a.b[i][k] * b.b[k][j];
            }
        }
    }
    return ans;
}
double matrix_pow(matrix a, int b)
{
    matrix ans;
    ans.b[0][0] = 1;
    ans.b[0][1]=0;;
    ans.b[1][0]=0;
    ans.b[1][1] = 1;
    while (b)
    {
        if (b & 1)
        {
            ans = chenfa(ans, a);
        }
        b /= 2;
        a = chenfa(a, a);
    }
    return ans.b[0][0];
}
int main()
{
    while (cin >> n >> p)
    {
        memset(dp, 0, sizeof dp);
        a[0] = 0;
        rep(i, 1, n)
        {
            cin >> a[i];
        }
        sort(a, a + n + 1);
        dp[0] = 1.0;
        matrix c = {p, 1 - p, 1, 0};
        rep(i, 1, n)
        {
            dp[i] = dp[i - 1] * (1 - matrix_pow(c, a[i] - a[i - 1] - 1));
        }
        printf("%.7f\n", dp[n]);
    }
}

B - Collecting Bugs

Ivan is fond of collecting. Unlike other people who collect post stamps, coins or other material stuff, he collects software bugs. When Ivan gets a new program, he classifies all possible bugs into n categories. Each day he discovers exactly one bug in the program and adds information about it and its category into a spreadsheet. When he finds bugs in all bug categories, he calls the program disgusting, publishes this spreadsheet on his home page, and forgets completely about the program. Two companies, Macrosoft and Microhard are in tight competition. Microhard wants to decrease sales of one Macrosoft program. They hire Ivan to prove that the program in question is disgusting. However, Ivan has a complicated problem. This new program has s subcomponents, and finding bugs of all types in each subcomponent would take too long before the target could be reached. So Ivan and Microhard agreed to use a simpler criteria --- Ivan should find at least one bug in each subsystem and at least one bug of each category. Macrosoft knows about these plans and it wants to estimate the time that is required for Ivan to call its program disgusting. It's important because the company releases a new version soon, so it can correct its plans and release it quicker. Nobody would be interested in Ivan's opinion about the reliability of the obsolete version. A bug found in the program can be of any category with equal probability. Similarly, the bug can be found in any given subsystem with equal probability. Any particular bug cannot belong to two different categories or happen simultaneously in two different subsystems. The number of bugs in the program is almost infinite, so the probability of finding a new bug of some category in some subsystem does not reduce after finding any number of bugs of that category in that subsystem. Find an average time (in days of Ivan's work) required to name the program disgusting.

Input

Input file contains two integer numbers, n and s (0 < n, s <= 1 000).

Output

Output the expectation of the Ivan's working days needed to call the program disgusting, accurate to 4 digits after the decimal point.

Sample

Inputcopy Outputcopy
1 2 3.0000

上一题求概率，因此是顺

本题求天数的期望，因此是逆推

题意：

一个程序员每天都可以找到一个 b u g，每个 b u g 都属于一个子系统及一个分类，且属于某个子系统的概率为 \(\frac{1}{s}\) ，属于某个分类的概率为\(\frac{1}{n}\) 。求该程序员发现了 n 种 b u g ，且属于 s个子系统的天数期望。

1
2
3
4
5
6
7
8
9
10
11
12
dp[i][j]状态可以转化成以下四种：
dp[i][j] 发现一个bug属于已经找到的i种bug和j个子系统中
dp[i+1][j] 发现一个bug属于新的一种bug，但属于已经找到的j种子系统
dp[i][j+1] 发现一个bug属于已经找到的i种bug，但属于新的子系统
dp[i+1][j+1]发现一个bug属于新的一种bug和新的一个子系统
以上四种的概率分别为：
p1 = i*j / (n*s)
p2 = (n-i)*j / (n*s)
p3 = i*(s-j) / (n*s)
p4 = (n-i)*(s-j) / (n*s)
dp[i,j] = p1*dp[i,j] + p2*dp[i+1,j] + p3*dp[i,j+1] + p4*dp[i+1,j+1] + 1;
化简后即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//一天只能发现一个bug
//属于子系统的概率是1/s
//属于分类的概率是1/n
//dp[i][j]表示已经找到i种bug并且存在于j种子系统里面的天数期望
//dp[n][s]=0
//dp[i][j]有四种可能
//找到的一个bug都已经出现过
//在两者中出现过一次
//都没有出现过
//四种情况
//反向枚举应该即可
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
const int N=1e3+100;
double dp[N][N];
int main()
{
int n,s;
while(cin>>n>>s)
{
dp[n][s]=0;
//初始化
frep(i,n,0)
{
    frep(j,s,0)
    {
        if(i==n&&j==s)
{
    continue;
}
double p1, p2, p3, p4;
p1 = (double)i * j / (n * s);       // dp[i][j];
p2 = (double)(n - i) * j / (n * s); // dp[i+1][j];
p3 = (double)i * (s - j) / (n * s); // dp[i][j+1];
p4 = (double)(n - i) * (s - j) / (n * s);
dp[i][j] = (1 + p2 * dp[i + 1][j] + p3 * dp[i][j + 1] + p4 * dp[i + 1][j + 1]) / (1 - p1);
    }
}
printf("%.4f\n", dp[0][0]);
}
}

C - One Person Game

There is a very simple and interesting one-person game. You have 3 dice, namely Die1, Die2 and Die3. Die1 has K1 faces. Die2 has K2 faces. Die3 has K3 faces. All the dice are fair dice, so the probability of rolling each value, 1 to K1, K2, K3 is exactly 1 / K1, 1 / K2 and 1 / K3. You have a counter, and the game is played as follow:

  1. Set the counter to 0 at first.
  2. Roll the 3 dice simultaneously. If the up-facing number of Die1 is a, the up-facing number of Die2 is b and the up-facing number of Die3 is c, set the counter to 0. Otherwise, add the counter by the total value of the 3 up-facing numbers.
  3. If the counter's number is still not greater than n, go to step 2. Otherwise the game is ended.

Calculate the expectation of the number of times that you cast dice before the end of the game.

Input

There are multiple test cases. The first line of input is an integer T (0 < T <= 300) indicating the number of test cases. Then T test cases follow. Each test case is a line contains 7 non-negative integers n, K1, K2, K3, a, b, c (0 <= n <= 500, 1 < K1, K2, K3 <= 6, 1 <= a <= K1, 1 <= b <= K2, 1 <= c <= K3).

Output

For each test case, output the answer in a single line. A relative error of 1e-8 will be accepted.

Sample Input

1
2
3
2
0 2 2 2 1 1 1
0 6 6 6 1 1 1

Sample Output

1
2
1.142857142857143
1.004651162790698

注意还是逆推

题意

有三个骰子，分别有k1,k2,k3个标号1−k的面，每次扔骰子，若三个面分别为a,b,c 则分数置为0，否则加上分数之和。

当分数大于0时游戏结束，问游戏结束的期望步数。

容易想到转移方程，令dp[i]表示当前分数为i 时，游戏结束的期望步数，则答案就是dp[0]

\(dp[i] = \sum p_k \cdot dp[i + k] + p_0 \cdot dp[0] + 1\)

由于无法表达出dp[0]

因此不妨设置

1
dp[i] = A[i] * dp[0] + B[i]

带入后

\(dp[i] = \sum p_k \cdot (A[i + k] \cdot dp[0]+B[i+k])+p_0*dp[0]+1 \\ =\sum (p_k \cdot A[i+k]+p_0)\cdot dp[0]+\sum (p_k \cdot B[i+k]) + 1\)

于是有

\(A[i] = \sum p_k \cdot A[i+k] + p_0,B[i] = \sum p_k \cdot B[i+k] + 1\)

递推求得A,B即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
using namespace std;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
using ll=long long;
const int N=1e6+100;
double p[N];
double a[N];
double b[N];
int main()
{
int t;
cin>>t;
while(t--)
{
    memset(p,0,sizeof(p));
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    int n,k1,k2,k3;
    int A,B,C;
    cin>>n>>k1>>k2>>k3>>A>>B>>C;
    p[0]=1.0/(k1*k2*k3);
    rep(i,1,k1)
    {
rep(j,1,k2)
{
    rep(k,1,k3)
    {
        if(i==A&&j==B&&k==C)
        {
            continue;
        }
        p[i+j+k]+=(1.0)/(k1*k2*k3);
    }
}
    }
    frep(i,n,0)
    {
        a[i]=p[0];
        b[i]=1;
rep(j,3,k1+k2+k3)
{
    a[i]+=a[i+j]*p[j];
    b[i]+=b[i+j]*p[j];
}
    }
printf("%.15lf\n",b[0]/(1-a[0]));
}

}

D - Aeroplane chess

Hzz loves aeroplane chess very much. The chess map contains N+1 grids labeled from 0 to N. Hzz starts at grid 0. For each step he throws a dice(a dice have six faces with equal probability to face up and the numbers on the faces are 1,2,3,4,5,6). When Hzz is at grid i and the dice number is x, he will moves to grid i+x. Hzz finishes the game when i+x is equal to or greater than N.

There are also M flight lines on the chess map. The i-th flight line can help Hzz fly from grid Xi to Yi (0<Xi<Yi<=N) without throwing the dice. If there is another flight line from Yi, Hzz can take the flight line continuously. It is granted that there is no two or more flight lines start from the same grid.

Please help Hzz calculate the expected dice throwing times to finish the game.

Input

There are multiple test cases. Each test case contains several lines. The first line contains two integers N(1≤N≤100000) and M(0≤M≤1000). Then M lines follow, each line contains two integers Xi,Yi(1≤Xi<Yi≤N). The input end with N=0, M=0.

Output

For each test case in the input, you should output a line indicating the expected dice throwing times. Output should be rounded to 4 digits after decimal point.

Sample

Inputcopy Outputcopy
2 0 8 3 2 4 4 5 7 8 0 0 1.1667 2.3441

期望dp，直接逆推即可

题意：

有编号为0-n的n+1个网格，每次扔骰子，骰子有6个面，分别标有1，2，3，4，5，6.每一面的概率都是1/6.根据骰子的点数从0开始向前走，知道走到大于等于n结束。同时网格上有些格子会直接跳到下个格子，此时不需要扔骰子。问结束游戏需要仍多少次骰子。

思路： dp[i]表示在i点到N点的期望值，dp[n]=0，求dp[0]，没有飞路线的情况下dp[i]=dp[i+1]/6+dp[i+2]/6+...+dp[i+6]/6+1，倒推求解即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// 这题相对比较好推理
// 直接转就行
// 能跳就跳
// 不能的话直接转移，以1/6的概率进行转移即可
#include <iostream>
#include <algorithm>
#include <string.h>
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
using ll = long long;
using namespace std;
const int N = 1e6 + 100;
int n, m;
int go[N];
double dp[N];
double p = 1.0 / 6.0;
int main()
{
    while (cin >> n >> m)
    {
        if (n == 0 && m == 0)
        {
            break;
        }
        memset(dp, 0, sizeof(dp));
        memset(go, -1, sizeof go);
        while (m--)
        {
            int x, y;
            cin >> x >> y;
            go[x] = y;
        }
        frep(i, n - 1, 0)
        {
            if (go[i] != -1)
            {
                dp[i] = dp[go[i]];
            }
            else
            {
                dp[i] = p * (dp[i + 1] + dp[i + 2] + dp[i + 3] + dp[i + 4] + dp[i + 5] + dp[i + 6])+1.0;
            }
        }
        printf("%.4f\n", dp[0]);
    }
    return 0;
}

G - LOOPS

Akemi Homura is a Mahou Shoujo (Puella Magi/Magical Girl).

Homura wants to help her friend Madoka save the world. But because of the plot of the Boss Incubator, she is trapped in a labyrinth called LOOPS. img The planform of the LOOPS is a rectangle of R*C grids. There is a portal in each grid except the exit grid. It costs Homura 2 magic power to use a portal once. The portal in a grid G(r, c) will send Homura to the grid below G (grid(r+1, c)), the grid on the right of G (grid(r, c+1)), or even G itself at respective probability (How evil the Boss Incubator is)! At the beginning Homura is in the top left corner of the LOOPS ((1, 1)), and the exit of the labyrinth is in the bottom right corner ((R, C)). Given the probability of transmissions of each portal, your task is help poor Homura calculate the EXPECT magic power she need to escape from the LOOPS.

Input

The first line contains two integers R and C (2 <= R, C <= 1000).

The following R lines, each contains C*3 real numbers, at 2 decimal places. Every three numbers make a group. The first, second and third number of the cth group of line r represent the probability of transportation to grid (r, c), grid (r, c+1), grid (r+1, c) of the portal in grid (r, c) respectively. Two groups of numbers are separated by 4 spaces.

It is ensured that the sum of three numbers in each group is 1, and the second numbers of the rightmost groups are 0 (as there are no grids on the right of them) while the third numbers of the downmost groups are 0 (as there are no grids below them).

You may ignore the last three numbers of the input data. They are printed just for looking neat.

The answer is ensured no greater than 1000000.

Terminal at EOF

Output

A real number at 3 decimal places (round to), representing the expect magic power Homura need to escape from the LOOPS.

Sample

Inputcopy Outputcopy
2 2 0.00 0.50 0.50 0.50 0.00 0.50 0.50 0.50 0.00 1.00 0.00 0.00 6.000

题意：给定一个矩阵，从 (1,1) 出发，有一定几率留在原地、向下走，向右走，求走到 (r,c) 平均要走多少步 (每次移动算两步)？

1
2
3
4
设 dp[i][j] 为 (i,j) 走到 (r,c) 的期望步数，p[i][j][k] 为 (i,j) 向方向 k 的移动几率，那么
dp[i][j]=dp[i+1][j]×p[i][j][1] + dp[i][j+1]×p[i][j][2] + dp[i][j]*p[i][j][3] + 2
由于我们要从 dp[i+1][j],dp[i][j+1] 推出 dp[i][j], 所以经过移项：
dp[i][j]=(dp[i+1][j]×p[i][j][1] + dp[i][j+1]×p[i][j][2] + 2)/(1-p[i][j][3]);
1
然而，为什么我们不能设 dp[i][j] 为走到 (i,j) 的期望步数而从 dp[i-1][j],dp[i][j-1] 推出 dp[i][j] 呢？因为你不知道出现在 (i,j-1) 的概率是多少，因此递推的过程将是不完备、不稳定、不正确的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
//设dp[i][j]走到(i,j)的期望步数
//p[i][j][k]为(i,j)以k的方式去走的概率
//这样子就可以直接递推了
//dp[i][j]=dp[i+1][j]*p[i][j][1]+dp[i][j+1]*p[i][j][2]+dp[i][j]*p[i][j][3]+2
#include<iostream>
#include<algorithm>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
const int N=1e3+10;
double dp[N][N];
double p[N][N][4];
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    while (cin >> n >> m)
    {
        rep(i, 1, n)
        {
            rep(j, 1, m)
            {
                scanf("%lf%lf%lf", &p[i][j][1], &p[i][j][2], &p[i][j][3]);
            }
        }
        dp[n][m] = 0;
        frep(i, n, 1)
        {
            frep(j, m, 1)
            {
                if (i == n && j == m||p[i][j][1]==1)
                {
                    continue;
                }
                dp[i][j] = (dp[i + 1][j] * p[i][j][3] + dp[i][j + 1] * p[i][j][2] + 2) / (1 - p[i][j][1]);
            }
        }
        printf("%.3lf\n", dp[1][1]);
}
return 0;
}

H - Check the difficulty of problems

Organizing a programming contest is not an easy job. To avoid making the problems too difficult, the organizer usually expect the contest result satisfy the following two terms:

  1. All of the teams solve at least one problem.
  2. The champion (One of those teams that solve the most problems) solves at least a certain number of problems.

Now the organizer has studied out the contest problems, and through the result of preliminary contest, the organizer can estimate the probability that a certain team can successfully solve a certain problem.

Given the number of contest problems M, the number of teams T, and the number of problems N that the organizer expect the champion solve at least. We also assume that team i solves problem j with the probability Pij (1 <= i <= T, 1<= j <= M). Well, can you calculate the probability that all of the teams solve at least one problem, and at the same time the champion team solves at least N problems?

Input

The input consists of several test cases. The first line of each test case contains three integers M (0 < M <= 30), T (1 < T <= 1000) and N (0 < N <= M). Each of the following T lines contains M floating-point numbers in the range of [0,1]. In these T lines, the j-th number in the i-th line is just Pij. A test case of M = T = N = 0 indicates the end of input, and should not be processed.

Output

For each test case, please output the answer in a separate line. The result should be rounded to three digits after the decimal point.

Sample

Inputcopy Outputcopy
2 2 2 0.9 0.9 1 0.9 0 0 0 0.972

题意：

ACM比赛中，共M道题，T个队，pij表示第i队解出第j题的概率，问 每队至少解出一题且冠军队至少解出N道题的概率。

假设ans1为每个队至少解出一题的概率。

假设ans2为每个队解出的题数均在 [1.n-1] 之间的概率。

这样最终答案就是ans1-ans2。

ans1可以在读入的数据中预处理出来，ans2通过dp求解。

dp[i] [j] [k]表示第i个队在第j个题中解出k个题的概率。

其余看代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// 计算出每一只队伍至少解决一个问题
// 计算出每一只队伍解决1-n-1个问题
// 注意要初始化
// dp[i][j][0]=dp[i][j-1][0]*(1-p[i][j])
// dpp[i][0][0]=1
// 一般情况：  dp[i][j][k]=dp[i][j-1][k]*(1-p[i][j])+dp[i][j-1][k-1]*p[i][j];
#include <iostream>
#include <string.h>
#include <stdio.h>
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
using namespace std;
const int N=1005;
double p[N][33];
double dp[N][33][33];
double ans1,ans2;
double mid;
int m,t,n;
int main()
{
while(cin>>m>>t>>n)
{
    ans1 = 1;
    ans2 = 1;
    if (m == 0 && t == 0 && n == 0)
    {
        break;
}
rep(i,1,t)
{
    mid=1;
    rep(j,1,m)
    {
cin>>p[i][j];
mid*=(1-p[i][j]);
    }
    ans1*=(1-mid);
}
rep(i,1,t)
{
    dp[i][0][0]=1;
    rep(j,1,m)
    {
        dp[i][j][0]=dp[i][j-1][0]*(1-p[i][j]);
        rep(k,1,m)
        {
            dp[i][j][k]=dp[i][j-1][k]*(1-p[i][j])+dp[i][j-1][k-1]*p[i][j];
        }
    }
}
rep(i,1,t)
{
    mid=0;
    rep(j,1,n-1)
    {
        mid+=dp[i][m][j];
    }
    ans2*=mid;
}
printf("%.3f\n", ans1 - ans2);
}
return 0;
}

I - Bag of mice

The dragon and the princess are arguing about what to do on the New Year's Eve. The dragon suggests flying to the mountains to watch fairies dancing in the moonlight, while the princess thinks they should just go to bed early. They are desperate to come to an amicable agreement, so they decide to leave this up to chance.

They take turns drawing a mouse from a bag which initially contains w white and b black mice. The person who is the first to draw a white mouse wins. After each mouse drawn by the dragon the rest of mice in the bag panic, and one of them jumps out of the bag itself (the princess draws her mice carefully and doesn't scare other mice). Princess draws first. What is the probability of the princess winning?

If there are no more mice in the bag and nobody has drawn a white mouse, the dragon wins. Mice which jump out of the bag themselves are not considered to be drawn (do not define the winner). Once a mouse has left the bag, it never returns to it. Every mouse is drawn from the bag with the same probability as every other one, and every mouse jumps out of the bag with the same probability as every other one.

Input

The only line of input data contains two integers w and b (0 ≤ w, b ≤ 1000).

Output

Output the probability of the princess winning. The answer is considered to be correct if its absolute or relative error does not exceed 10 - 9.

Sample 1

Inputcopy Outputcopy
1 3 0.500000000

Sample 2

Inputcopy Outputcopy
5 5 0.658730159

Note

Let's go through the first sample. The probability of the princess drawing a white mouse on her first turn and winning right away is 1/4. The probability of the dragon drawing a black mouse and not winning on his first turn is 3/4 * 2/3 = 1/2. After this there are two mice left in the bag — one black and one white; one of them jumps out, and the other is drawn by the princess on her second turn. If the princess' mouse is white, she wins (probability is 1/2 * 1/2 = 1/4), otherwise nobody gets the white mouse, so according to the rule the dragon wins.

题意

袋子里有ww 只白鼠和bb 只黑鼠 ，A和B轮流从袋子里抓，谁先抓到白色谁就赢。A每次随机抓一只，B每次随机抓完一只之后会有另一只随机老鼠跑出来。如果两个人都没有抓到白色则B赢。A先抓，问A赢的概率。

题解我认为这一篇写的很详细，直接看就好

image-20240317220554992 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
//有白鼠
//黑鼠
//谁先抓白就赢了
//一个人随机抓一只
//另有一个人抓完一只就会跑一只出来
//i只白老鼠，j只黑老鼠
#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdio.h>
using namespace std;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
const int N=1e3+100;
double dp[N][N];
int main()
{
int w,b;
cin>>w>>b;
rep(i,1,w)
{
    dp[i][0]=1;
}
rep(i,1,b)
{
    dp[0][i]=0;
}
rep(i,1,w)
{
    rep(j,1,b)
    {
        dp[i][j]+=(double)i/(i+j);
        if (j >= 3)
        {
            dp[i][j] += (double)j / (i + j) * (j - 1) / (i + j - 1) * (j - 2) /(i + j - 2) * dp[i][j - 3];
        }
        if (i >= 1 && j >= 2)
        {
            dp[i][j] += (double)j / (i + j) * (j - 1) / (i + j - 1) * i /(i + j - 2) * dp[i - 1][j - 2];
        }
}
}
printf("%.9lf\n", dp[w][b]);
return 0;
}

J - Football

Consider a single-elimination football tournament involving 2n teams, denoted 1, 2, …, 2n. In each round of the tournament, all teams still in the tournament are placed in a list in order of increasing index. Then, the first team in the list plays the second team, the third team plays the fourth team, etc. The winners of these matches advance to the next round, and the losers are eliminated. After n rounds, only one team remains undefeated; this team is declared the winner.

Given a matrix P = [pij] such that pij is the probability that team i will beat team j in a match determine which team is most likely to win the tournament.

Input

The input test file will contain multiple test cases. Each test case will begin with a single line containing n (1 ≤ n ≤ 7). The next 2n lines each contain 2n values; here, the jth value on the ith line represents pij. The matrix P will satisfy the constraints that pij = 1.0 − pji for all i ≠ j, and pii = 0.0 for all i. The end-of-file is denoted by a single line containing the number −1. Note that each of the matrix entries in this problem is given as a floating-point value. To avoid precision problems, make sure that you use either the double data type instead of float.

Output

The output file should contain a single line for each test case indicating the number of the team most likely to win. To prevent floating-point precision issues, it is guaranteed that the difference in win probability for the top two teams will be at least 0.01.

Sample

Inputcopy Outputcopy
2 0.0 0.1 0.2 0.3 0.9 0.0 0.4 0.5 0.8 0.6 0.0 0.6 0.7 0.5 0.4 0.0 -1 2

Hint

In the test case above, teams 1 and 2 and teams 3 and 4 play against each other in the first round; the winners of each match then play to determine the winner of the tournament. The probability that team 2 wins the tournament in this case is:

P(2 wins) = P(2 beats 1)P(3 beats 4)P(2 beats 3) + P(2 beats 1)P(4 beats 3)P(2 beats 4) = p21p34p23 + p21p43p24 = 0.9 · 0.6 · 0.4 + 0.9 · 0.4 · 0.5 = 0.396.

The next most likely team to win is team 3, with a 0.372 probability of winning the tournament.

题意：

\(2*n\)只球队,按顺序依次进行比赛,一轮下来,胜利的队伍再按顺序依次进行比赛,给出i队战胜j队的概率

求一个最大概率赢的队伍

由于此时比赛过的队伍不能重复，所以运用二进制将其按顺序比赛

1
(j>>(i-1))==(k>>(i-1)^1)
1
2
3
dp[i][j]:第j个队伍在第i场获胜的概率
求其获胜概率可以推出式子：
dp[i][j]+=dp[i-1][j]*dp[i-1][k]*p[j][k]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
// 搞不懂为什么开同步流那么慢
// 老是t我
#include <iostream>
#include <algorithm>
#include <string.h>
#include <stdio.h>
// 注意dp[i][j]表示第i轮比赛里面，j球队能够赢得比赛的概率
using namespace std;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
const int N = 1e3 + 100;
double dp[N][N];
double p[N][N];
int main()
{
    int n;
    while (scanf("%d", &n))
    {
        if(n<0)
        {
            break;
        }
        int len=1<<n;
        rep(i,1,len)
        {
            rep(j,1,len)
            {
                scanf("%lf", &p[i][j]);
            }
        }
        memset(dp,0,sizeof dp);
        rep(i,1,len)
        {
            dp[0][i]=1;
        }
        //还未开始比赛都为1
        rep(i,1,n)
        {
            rep(j,1,len)
            {
                rep(k,1,len)
                {
                    if((((j-1)>>(i-1))^1)==((k-1)>>(i-1)))
                    //判断相邻的异或技巧
                    {
                       dp[i][j]+=dp[i-1][j]*dp[i-1][k]*p[j][k];
                    }
                }
            }
        }
        double maxn=0;
        int ans;
        rep(i,1,len)
        {
            if(dp[n][i]>maxn)
            {
                maxn=dp[n][i];
                ans=i;
            }
        }
        printf("%d\n", ans);
    }
}




//以下为cin,cout版本
#include <iostream>
#include <algorithm>
#include <string.h>
#include <stdio.h>
// 注意dp[i][j]表示第i轮比赛里面，j球队能够赢得比赛的概率
using namespace std;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
const int N = 1e3 + 100;
double dp[N][N];
double p[N][N];
int main()
{
    int n;
    while (cin >> n)
    {
        if (n == -1)
        {
            break;
        }
        int len = 1 << n;
        rep(i, 1, len)
        {
            rep(j, 1, len)
            {
                cin >> p[i][j];
            }
        }
        memset(dp, 0, sizeof dp);
        rep(i, 1, len)
        {
            dp[0][i] = 1;
        }
        // 还未开始比赛都为1
        rep(i, 1, n)
        {
            rep(j, 1, len)
            {
                rep(k, 1, len)
                {
                    if (((j - 1) >> (i - 1) ^ 1) == ((k - 1) >> (i - 1)))
                    // 判断相邻的异或技巧
                    {
                       dp[i][j] += dp[i - 1][j] * dp[i - 1][k] * p[j][k];
                       //j和k在上一轮活下来，并且j打败了k
                    }
                }
            }
        }
        double maxn = 0;
        int ans;
        rep(i, 1, len)
        {
            if (dp[n][i] > maxn)
            {
                maxn = dp[n][i];
                ans = i;
            }
        }
        cout << ans << '\n';
    }
}

K - Kids and Prizes

ICPC (International Cardboard Producing Company) is in the business of producing cardboard boxes. Recently the company organized a contest for kids for the best design of a cardboard box and selected M winners. There are N prizes for the winners, each one carefully packed in a cardboard box (made by the ICPC, of course). The awarding process will be as follows:

  • All the boxes with prizes will be stored in a separate room.
  • The winners will enter the room, one at a time.
  • Each winner selects one of the boxes.
  • The selected box is opened by a representative of the organizing committee.
  • If the box contains a prize, the winner takes it.
  • If the box is empty (because the same box has already been selected by one or more previous winners), the winner will instead get a certificate printed on a sheet of excellent cardboard (made by ICPC, of course).
  • Whether there is a prize or not, the box is re-sealed and returned to the room.

The management of the company would like to know how many prizes will be given by the above process. It is assumed that each winner picks a box at random and that all boxes are equally likely to be picked. Compute the mathematical expectation of the number of prizes given (the certificates are not counted as prizes, of course).

Input

The first and only line of the input file contains the values of N and M (img).

Output

The first and only line of the output file should contain a single real number: the expected number of prizes given out. The answer is accepted as correct if either the absolute or the relative error is less than or equal to 10-9.

Sample 1

Inputcopy Outputcopy
5 7 3.951424

Sample 2

Inputcopy Outputcopy
4 3 2.3125

题意：

有n个奖品，m个人排队来选礼物，礼物拿完盒子放回，对于每个人，他打开的盒子，可能有礼物，也有可能已经被之前的人取走了。求最后m个人取走礼物的期望

第一个人取礼物时，随便怎么取，肯定是有的，所以dp[1] = 1; 第i个人取礼物时，那么前面已经取走了dp[i-1]个了，那么他取到的概率是(n-dp[i-1])/n，dp[i]还得加上dp[i-1]

于是转移方程：dp[i] = (n-dp[i-1])/n+dp[i-1];

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//dp[i]表示到第i个人后取得的奖品
//这道应该是最水的
#include <iostream>
#include <algorithm>
#include <string.h>
#include <stdio.h>
using namespace std;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
const int N = 1e6 + 100;
double dp[N];
//dp[i]=dp[i+1]+(n-dp[i-1])/n*1+dp[i-1]/n*0
int main()
{
int n,m;
cin>>n>>m;
dp[1]=1.0;
//n个奖品一开始总能抽到
rep(i,2,m)
{
dp[i]=(n-dp[i-1])/n+dp[i-1];
}
printf("%.10f\n",dp[m]);
}

M - Help Me Escape

Background

If thou doest well, shalt thou not be accepted? and if thou doest not well, sin lieth at the door. And unto thee shall be his desire, and thou shalt rule over him. And Cain talked with Abel his brother: and it came to pass, when they were in the field, that Cain rose up against Abel his brother, and slew him. And the LORD said unto Cain, Where is Abel thy brother? And he said, I know not: Am I my brother's keeper? And he said, What hast thou done? the voice of thy brother's blood crieth unto me from the ground. And now art thou cursed from the earth, which hath opened her mouth to receive thy brother's blood from thy hand; When thou tillest the ground, it shall not henceforth yield unto thee her strength; a fugitive and a vagabond shalt thou be in the earth.

—— Bible Chapter 4

Now Cain is unexpectedly trapped in a cave with N paths. Due to LORD's punishment, all the paths are zigzag and dangerous. The difficulty of the ith path is ci.

Then we define f as the fighting capacity of Cain. Every day, Cain will be sent to one of the N paths randomly.

Suppose Cain is in front of the ith path. He can successfully take ti days to escape from the cave as long as his fighting capacity f is larger than ci. Otherwise, he has to keep trying day after day. However, if Cain failed to escape, his fighting capacity would increase ci as the result of actual combat. (A kindly reminder: Cain will never died.)

As for ti, we can easily draw a conclusion that ti is closely related to ci. Let's use the following function to describe their relationship:

img

After D days, Cain finally escapes from the cave. Please output the expectation of D.

Input

The input consists of several cases. In each case, two positive integers N and f (n ≤ 100, f ≤ 10000) are given in the first line. The second line includes N positive integers ci (ci ≤ 10000, 1 ≤ i ≤ N)

Output

For each case, you should output the expectation(3 digits after the decimal point).

Sample

Inputcopy Outputcopy
3 1 1 2 3 6.889

题意：一个战士初始有 f 点攻击力，每一天都会被随机分到 n 个洞穴（概率等同），每个洞穴有相应的困难值 ci ， 若 f > ci ，则战士可以花费 ti 天的时间攻破洞穴，完成试验，否则花费一天的时间把攻击力 + ci ，然后重新试验， 求完成试验的期望天数

题见上

设 dp[ f ] 表示攻击力为 f 完成试验的期望，则存在两种情况

① f > ci , dp[ f ] + = ti / n ;

② f<=ci , dp[ f ] + = ( 1 + dp [ i + ci ] ) / n ;

因为当前攻击力 f 的变化不规律，所以借助记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <algorithm>
#include <string.h>
#include <stdio.h>
#include<math.h>
using namespace std;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
const int N=1e6+100;
int n;
double dp[N];
//没开double 
//于是半小时过去了
int t[N];
//预处理出来的
//f > ci, dp[f] + = ti / n;
//f <= ci, dp[f] + = (1 + dp[i + ci]) / n;
int f;
int c[N];

double dfs(int f)
{
    if (dp[f])
        return dp[f];

    for (int i = 1; i <= n; i++)
    {
        if (f > c[i])
        {
            dp[f] += (double)t[i] / n;
        }
        else
        {
            dp[f] += (1 + dfs(f + c[i])) / n;
        }
    }
    return dp[f];
} 
int main()
{
    while(cin>>n>>f)
    {
        rep(i,1,n)
        {
            cin>>c[i];
            t[i] = (1.0 + sqrt(5)) / 2 * c[i] * c[i];
        }
        memset(dp, 0, sizeof(dp));
        printf("%.3f\n", dfs(f));
    }
}
img