大意
有7个州，每个州有 (x_i) 个选民，每个选民随机投给A党或B党（概率各50%），若某州A党得票多于B党，则A赢该州；若平局，则B党赢，求A党赢得至少4个州的概率。
核心分析
每个州的结果独立,因此问题可拆解为两步：
- 计算每个州A党获胜的概率 (p_i)；
- 计算7个独立事件中至少4次成功（A赢州）的概率。
步骤1：计算单个州的获胜概率 (p_i)
对于州 (i)（选民数 (x_i)）：
- 若 (x_i) 为奇数：总票数为奇数，无平局，A、B获胜概率对称，故 (p_i = 0.5)；
- 若 (x_i) 为偶数：设 (x_i = 2m)，A获胜需得票 > (m)。
[ p_i = \frac{1 - \frac{\binom{2m}{m}}{2^{2m}}}{2} ]
(\binom{2m}{m}/2^{2m}) 是平局概率，利用斯特林公式近似：
[ \binom{2m}{m} \approx \frac{2^{2m}}{\sqrt{\pi m}} \implies \frac{\binom{2m}{m}}{2^{2m}} \approx \frac{1}{\sqrt{\pi m}} ]
(p_i \approx \frac{1 - \frac{1}{\sqrt{\pi m}}}{2})。
步骤2：计算组合概率
由于7个州数量少,可通过动态规划计算至少4次成功的概率：
- 定义 (dp[j]) 为赢 (j) 个州的概率；
- 初始化 (dp[0] = 1.0)；
- 遍历每个州的 (p_i)，更新dp：
[ dp[j+1] += dp[j] p_i \quad \text{（赢当前州）} \ dp[j] = (1-p_i) \quad \text{（输当前州）} ] - 最终结果为 (sum(dp[4..7]))。
实现细节
- 浮点数精度：对于大 (m)（如 (1e9)），(\frac{1}{\sqrt{\pi m}}) 趋近于0，(p_i) 近似0.5；
- 枚举所有可能的组合（7个州选4-7个）：总共有 (C(7,4)+C(7,5)+C(7,6)+C(7,7)=64) 种，直接枚举也可行，但DP更高效。
示例代码片段
import math
x = list(map(int, input().split()))
p_list = []
for xi in x:
if xi % 2 == 1:
p = 0.5
else:
m = xi // 2
term = 1.0 / math.sqrt(math.pi * m)
p = (1 - term) / 2.0
p_list.append(p)
dp = [0.0] * 8
dp[0] = 1.0
for p in p_list:
# 逆序更新避免覆盖
for j in range(7, -1, -1):
if dp[j] == 0:
continue
dp[j+1] += dp[j] * p
dp[j] *= (1 - p)
ans = sum(dp[4:8])
print("{0:.10f}".format(ans))
本题通过数学推导简化了单个州的概率计算,再利用动态规划高效求解组合概率，关键在于理解奇偶情况下的概率对称性，以及斯特林公式对大组合数的近似处理，确保在大输入下仍能快速得到结果。
