把得分 2^{r+c} 按二项式展成「黑行/黑列子集」的计数,再用期望线性性枚举指定的 i 行 j 列全黑,用超几何概率 P(t)=∏(k−p)/(m−p) 在 O(n^2) 内求和。
OJ: roj
题目 ID: 1814
难度:提高+/省选-
标签:数学期望组合数学python
创建: 2026-10-08 06:15
更新: 2026-10-08 06:15
形式化题目
棋盘是
约束:
把随机过程拆成两个独立部分会更好用:
- 填数:
到 个格子的均匀随机单射; - 选数:
的均匀随机 子集 。
格子黑
正解
思路
朴素做法为什么走不通。 最直白的写法是分别算出"恰好
问题的根源在于:
关键跳跃一:把
这个代数式有非常干净的组合意义:从已经全黑的
把
其中
关键跳跃二:期望的线性性替换掉"恰好"。 对上面这个恒等式两边取期望, 指示函数的期望就是事件概率,求和可以和期望交换:
右边的事件只要求"指定的这些行、这些列全黑",不要求别的行/列不黑,因此不再需要容斥。
这正是它比
归并成
算概率
这
最右侧的连乘形式最容易在程序里递推:
对照两个特例确认公式。
数值精度。 double(上限约 double 范围内不会上溢。反过来,
代码
Python 版:
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 06:16
# update_at: 2026-10-08 06:16
import sys
CAP = 1e99 # 题面规定的答案上限,超过就原样输出它
def expected_score(n: int, m: int, k: int) -> float:
"""枚举"指定的 i 行 j 列全黑",求和得到 E[2^(r+c)](二项式展开消掉容斥)。"""
choose = [1.0] * (n + 1) # choose[i] = C(n,i),最大约 9.4e88,只有 float 装得下
for i in range(1, n + 1):
choose[i] = choose[i - 1] * (n - i + 1) / i
# cover_prob[t] = Π_{p<t} (k-p)/(m-p),即"指定的 t 个格子全黑"的概率。
# t > k 时选不出这么多数字,概率为 0,所以这些位置保持初值 0 不必特判。
cover_prob = [1.0] + [0.0] * (n * n)
for t in range(1, min(n * n, k) + 1):
cover_prob[t] = cover_prob[t - 1] * (k - t + 1) / (m - t + 1)
return sum(
choose[i] * choose[j] * cover_prob[n * (i + j) - i * j] # t = ni+nj-ij 格
for i in range(n + 1)
for j in range(n + 1)
)
def solve() -> None:
n, m, k = map(int, sys.stdin.buffer.read().split())
print(f"{min(expected_score(n, m, k), CAP):.10e}")
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-08 06:16
* update_at: 2026-10-08 06:16
*/
/*
* 一本通 1814 「方格染色」 —— 期望的线性性 + 二项式展开,O(n^2)
*
* 记 r 为被整行涂黑的行数,c 为被整列涂黑的列数,要求 E[2^(r+c)]。
* 关键恒等式:2^(r+c) = (1+1)^r * (1+1)^c = Σ_{R⊆黑行} Σ_{C⊆黑列} 1,
* 即 "得分" 等于 "黑行集合的子集数 × 黑列集合的子集数"。
* 于是取期望后可以直接枚举 "指定的 i 行 j 列全黑" 这一事件,绕开容斥:
*
* E = Σ_{i=0..n} Σ_{j=0..n} C(n,i)·C(n,j)·P(指定的 i 行 j 列全黑)
*
* 这 i 行 j 列覆盖的格子数为 t = n·i + n·j − i·j(行并列的并集),
* 指定 t 个格子的取值构成 [m] 的均匀 t-子集,全黑等价于它落在选出的 k 个数里:
*
* P(t) = C(m−t, k−t)/C(m,k) = Π_{p=0..t−1} (k−p)/(m−p),t > k 时 P(t) = 0
*
* 数值注意:C(300,150) ≈ 9.4e88 远超 long long,所以组合数与概率全程用 double;
* double 上限 1.7e308,单项最大约 9.4e88 × 9.4e88 × 1 ≈ 8.8e177,不会溢出。
* P(t) 在连乘中下溢成 0 时,该项 < 1e-130,远小于答案下界 1,可以安全忽略。
*/
#include <cstdio>
#include <algorithm>
typedef long long ll;
const int MAXN = 305; // n ≤ 300,多开一点留余量
const int MAXT = 90005; // 覆盖格子数 t ≤ n^2 ≤ 90000
double comb[MAXN][MAXN]; // comb[i][j] = C(i,j),帕斯卡三角形(double 存储,不会溢出)
double prob[MAXT]; // prob[t] = P(指定的 t 个格子全黑),题面要求 t ≤ m
int main() {
ll n, m, k;
if (scanf("%lld %lld %lld", &n, &m, &k) != 3) return 1;
// comb 用 Pascal 递推:C(i,j) = C(i-1,j-1) + C(i-1,j)
for (ll i = 0; i <= n; i++) {
comb[i][0] = 1.0;
for (ll j = 1; j <= i; j++)
comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
}
// prob[t] = Π_{p=0..t-1} (k-p)/(m-p);t > k 时选不出这么多数,概率为 0
ll tmax = std::min(n * n, k);
prob[0] = 1.0;
for (ll t = 1; t <= tmax; t++)
prob[t] = prob[t - 1] * (double)(k - t + 1) / (double)(m - t + 1);
double sum = 0.0;
for (ll i = 0; i <= n; i++) {
for (ll j = 0; j <= n; j++) {
ll t = n * i + n * j - i * j; // 指定 i 行 j 列覆盖的格子数
if (t > k) continue; // 概率为 0,直接跳过
sum += comb[n][i] * comb[n][j] * prob[t];
}
}
if (sum > 1e99) sum = 1e99; // 题面要求答案超过 1e99 时输出 1e99
printf("%.10e\n", sum);
return 0;
}复杂度
- 时间:组合数
次递推(只用到 一行,用比值递推而非帕斯卡三角), 概率数组 次连乘,双重求和 。总计 , 时约 项,C++ 实测 9 ms、Python 实测 30 ms(限时 1000 ms)。 - 空间:
choose与cover_prob各一个一维数组,与 ; C++ 版用静态数组 ,实测峰值内存 8.3 MB(限时 256 MB)。 - 与 C++ 解法的关系:
main.py与main.cpp是同一算法的两种落地, 复杂度同为,Python 版把帕斯卡三角换成比值递推、把二重循环收进生成器, 常数更小。本题 ,Python 实测 0.03 秒,不存在 TLE 风险。
总结
- "恰好"很难,"指定"很容易:
需要 的多维容斥, 而 只要求覆盖的 格全黑。 期望的线性性把前者换成后者,是本解法的全部杠杆。 是"子集计数": 就是" 个全黑行的子集个数"。 这一步把得分从"指数型的随机量"变成"对子集的指示函数之和", 从而可以逐子集取期望,不再需要先知道 、 的分布。 : 、系数为 的多项式看似平凡,却正好等于"所有子集求和"; 见到 可以条件反射地往"子集计数"上想。 - 不管集合怎么叠,先数并集大小:
行 列的覆盖格子数是 , 交叉部分被算了两次要减掉一次。这是所有"行列并集"型题目的通用一步。 - 精度先算量级再选类型:
直接决定了 不能用整型、必须用 double;而形式的下溢因为答案有下界 所以无害。 这两件事不看数量级是猜不出来的。 - 关于本题数据来源的说明:仓库内该题的
content.md题为"一本通 1814 方格染色" (见素材源头部注释,5 轮检索未找到公开题解/AC 代码),随仓data/由data.py生成, 题面亦可能是网络重建,出题意图与官方原题可能存在偏差。 本文的算法已用独立暴力程序核对:对穷举全部 种 (棋盘排列 选数集合),结果 时 、 时 ,与公式一致; 另在 、 上随机抽 全枚举对拍 120 组, 一致。 随仓 10 个数据点主解全部通过(逐字节相同), main.py逐点输出与.out也完全一致。