Problem C
Probability Computation
Input File: pc.in
Time Limit: 1 second
Problem Description
A random binary number X contains n independent random binary digits (bits) denoted
by b1 , b2 , b3 , · · · , bn , where b1 is the most significant bit and bn is the least significant bit.
That is, the value of X is b1 2n−1 + b2 2n−2 + b3 2n−3 + · · · + bn 20 . For each i, the random bit
bi is 1 with probability pi percents (0 ≤ pi ≤ 100) and bi is 0 with probability (100 − pi )
percents. Given the integer n (1 ≤ n ≤ 200), the integers p1 , p2 , p3 , · · · , pn , and the integers
Q (2 ≤ Q ≤ 99) and R (0 ≤ R < Q), your program should output the probability of the
event that X mod Q is equal to R, where mod is the modulus operation. In other words,
your program should output the probability P r{X mod Q = R}. The output probability
must be rounded to 5 digits after the decimal point.
For example, consider a test case with (n, p1 , p2 , p3 , p4 , Q, R) = (4, 0, 90, 100, 80, 5, 3).
Your program should output 0.08000, since
P r{X mod 5 = 3}
= P r{X = 3} + P r{X = 8} + P r{X = 13}
= P r{(b1 b2 b3 b4 ) = (0011)} + P r{(b1 b2 b3 b4 ) = (1000)} + P r{(b1b2 b3 b4 ) = (1101)}
= (100 − 0)% · (100 − 90)% · 100% · 80% + 0% · (100 − 90)% · (100 − 100)% · (100 − 80)% +
0% · 90% · (100 − 100)% · 80%
= 0.08000
Note: The above example is for explanation. The straightforward algorithm in the
example may not meet our time constraint when input integers are much larger. You should
develop another more efficient algorithm.
Technical Specification
The ranges of input integers are: 1 ≤ n ≤ 200, 0 ≤ pi ≤ 100 for each i, 2 ≤ Q ≤ 99, and
0 ≤ R < Q.
Input File Format
The first line of the input file contains an integer indicating the number of test cases to
follow. Then the input (n, p1 , p2 , p3 , · · · , pn , Q, R) of each test case is given in a separated
line. All integers are separated by one space.
Output Format
For each test case, your program should output the probability of the event that X mod Q is
equal to R in a separate line. The probability must be rounded to 5 digits after the decimal
point.
Sample Input
4
4 0 90 100 80 5 3
4 100 90 0 80 5 3
4 0 90 100 80 5 3
5 98 76 54 32 11 11 6
Sample Output
0.08000
0.74000
0.08000
0.25224
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAX = 101;
double dp[2 * MAX][MAX];
double P[2 * MAX];
/*
* 本题为概率DP，思想很简单dp[i][j],第一维为：i 代表
* 位数，第二维坐标为：j 代表余数，设该位取1的概率
* 为pi，那么状态转移方程为：
* dp[i+1][(j*2)%mod]+=dp[i][j]*(1-pi);
* dp[i+1][(j*2+1)%mod]+=dp[i][j]*pi;
* 这样写是为了便于理解，现在我们观察一下j的数据范围<100
* 我们可以很容易观察到能使用概率DP的特点，在狭小的平面上
* 逐步推进，最综得出的结果即是：dp[N][R], 一个很有启发的概
* 率题目，应该能撬动我们的概率dp大门。
*/
int main() {
int T;
int N, Q, R;
double temp;
scanf("%d", &T);
while (T--) {
scanf("%d", &N);
for (int i = 1; i <= N; i++) {
scanf("%lf", &temp);
P[i] = temp / 100;
}
scanf("%d%d", &Q, &R);
memset(dp, 0, sizeof (dp));
dp[1][1] = P[1];
dp[1][0] = 1 - P[1];
for (int i = 1; i < N; i++) {
for (int j = 0; j < Q; j++) {
dp[i + 1][(2 * j) % Q] += dp[i][j]*(1 - P[i + 1]);
dp[i + 1][(2 * j + 1) % Q] += dp[i][j] * P[i + 1];
}
}
printf("%.5lf\n", dp[N][R]);
}
return 0;
}