方格染色

GitHub跳转原题关系图返回列表

把得分 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

形式化题目

棋盘是 n×nn \times n 的 n2n^2 个互异格子,每个格子上均匀随机地填入 1∼m1 \sim m 中互不相同的数; 另外从 1∼m1 \sim m 中均匀随机地选出 kk 个数(可能选到没出现在棋盘上的数)。 凡是取值落在选中 kk 个数里的格子都被涂黑。设恰好被整行涂黑的行数为 rr、 被整列涂黑的列数为 cc,求 E[2 r+c]E\left[2^{\,r+c}\right]。

约束:2⩽n⩽3002 \leqslant n \leqslant 300,n2⩽m⩽100000n^2 \leqslant m \leqslant 100000,n⩽k⩽mn \leqslant k \leqslant m。 若答案 >1099> 10^{99} 则输出 109910^{99};输出与标准答案的相对误差不超过 10−610^{-6} 即算通过。

把随机过程拆成两个独立部分会更好用:

  1. 填数:{1,…,m}\{1,\dots,m\} 到 n2n^2 个格子的均匀随机单射;
  2. 选数:{1,…,m}\{1,\dots,m\} 的均匀随机 kk 子集 SS。

格子黑   ⟺  \iff 它的值 ∈S\in S。由于单射与子集抽样互相独立,任何指定的 tt 个格子的取值 构成 {1,…,m}\{1,\dots,m\} 的均匀 tt 子集,并且"这 tt 格全黑"只取决于 tt,与它们的具体位置无关。 这一点是整道题的地基。

正解

思路

朴素做法为什么走不通。 最直白的写法是分别算出"恰好 rr 行、cc 列全黑"的概率 P(r,c)P(r,c), 再乘 2r+c2^{r+c} 求和。可是"恰好"这个词要通过容斥才能消掉,而行与列在交叉格上互相纠缠: 固定 tt 行全黑时,列的统计并不独立。展开成"恰好"需要 O(22n)O(2^{2n}) 量级的多维容斥, n=300n = 300 时 26002^{600} 完全不可行。

问题的根源在于:rr 和 cc 是"恰好"量,而"恰好"天生难以直接计算。

关键跳跃一:把 2r+c2^{r+c} 换成一个计数。 注意 2=1+12 = 1+1,由二项式定理

2 r+c=2r⋅2c=(1+1)r(1+1)c=∑i=0r(ri)∑j=0c(cj)=∑i=0r∑j=0c(ri)(cj).2^{\,r+c} = 2^r \cdot 2^c = (1+1)^r (1+1)^c = \sum_{i=0}^{r}\binom{r}{i} \sum_{j=0}^{c}\binom{c}{j} = \sum_{i=0}^{r}\sum_{j=0}^{c}\binom{r}{i}\binom{c}{j}.

这个代数式有非常干净的组合意义:从已经全黑的 rr 行里挑 ii 行、从 cc 列里挑 jj 列的方案数, 恰好是 (ri)(cj)\binom{r}{i}\binom{c}{j}。也就是说

2 r+c=#{(R,C):R⊆全黑行,  ∣R∣=i,  C⊆全黑列,  ∣C∣=j}2^{\,r+c} = \#\{(R, C) : R \subseteq \text{全黑行},\; |R| = i,\; C \subseteq \text{全黑列},\; |C| = j\}

把 i,ji, j 也一并求和,等价于

2 r+c=∑R⊆[n]∑C⊆[n][每行 R 全黑∧每列 C 全黑],2^{\,r+c} = \sum_{R \subseteq [n]} \sum_{C \subseteq [n]} \bigl[\text{每行 } R \text{ 全黑} \wedge \text{每列 } C \text{ 全黑}\bigr],

其中 R,CR, C 遍历所有 2n⋅2n2^n \cdot 2^n 对子集,方括号是指示函数。这一步把"恰好 rr 行全黑" 这种全局条件,换成了对每一对具体子集 (R,C)(R, C) 的局部指示——容斥消失了。

关键跳跃二:期望的线性性替换掉"恰好"。 对上面这个恒等式两边取期望, 指示函数的期望就是事件概率,求和可以和期望交换:

E[2 r+c]=∑R⊆[n]∑C⊆[n]P(R 的每行全黑  ∧  C 的每列全黑).E\left[2^{\,r+c}\right] = \sum_{R \subseteq [n]} \sum_{C \subseteq [n]} P\bigl(R \text{ 的每行全黑} \;\wedge\; C \text{ 的每列全黑}\bigr).

右边的事件只要求"指定的这些行、这些列全黑",不要求别的行/列不黑,因此不再需要容斥。 这正是它比 P(r,c)P(r,c) 路线的优势:用线性性把"恰好"扔掉。

归并成 n2n^2 项。 由对称性,事件概率只取决于 ∣R∣=i|R| = i、∣C∣=j|C| = j, 而 ∣R∣=i|R| = i 的子集有 (ni)\binom{n}{i} 个:

E[2 r+c]=∑i=0n∑j=0n(ni)(nj)⋅P(指定的 i 行 j 列全黑).E\left[2^{\,r+c}\right] = \sum_{i=0}^{n}\sum_{j=0}^{n} \binom{n}{i}\binom{n}{j} \cdot P\bigl(\text{指定的 } i \text{ 行 } j \text{ 列全黑}\bigr).

算概率 P(t)P(t)。 指定的 ii 行和 jj 列在棋盘上占据的是它们的并集,格子数为

$t(i,j) = \underbrace{n\,i}_{\text{i$ 个整行}} + \underbrace{n,j}{\text{jj 个整列}} - \underbrace{i,j}{\text{交叉格算了两次}} .

这 tt 个格子的取值构成 {1,…,m}\{1,\dots,m\} 的均匀 tt 子集(单射保证互不相同), tt 格全黑   ⟺  \iff 选的 kk 个数把这 tt 个值全部包含进来。用超几何分布:

P(t)=(m−tk−t)(mk)=∏p=0t−1k−pm−p,t>k 时 P(t)=0.P(t) = \frac{\dbinom{m-t}{k-t}}{\dbinom{m}{k}} = \prod_{p=0}^{t-1}\frac{k-p}{m-p}, \qquad t > k \text{ 时 } P(t) = 0 .

最右侧的连乘形式最容易在程序里递推:P(0)=1P(0) = 1,P(t)=P(t−1)⋅k−t+1m−t+1P(t) = P(t-1)\cdot\dfrac{k-t+1}{m-t+1}。 注意 t⩽n2⩽mt \leqslant n^2 \leqslant m 保证了分母 m−p+1⩾m−n2+1>0m-p+1 \geqslant m-n^2+1 > 0,永不除零。

对照两个特例确认公式。 k=mk = m 时所有格子必黑,P(t)=1P(t) = 1,于是 E=∑i∑j(ni)(nj)=2n⋅2n=4n=22nE = \sum_i\sum_j \binom{n}{i}\binom{n}{j} = 2^n \cdot 2^n = 4^n = 2^{2n},与"r=c=nr=c=n 得 22n2^{2n}"一致。 k<nk < n 时 t⩾n>kt \geqslant n > k 恒成立,P(t)=0P(t) = 0,E=1E = 1,与"一行都涂不黑、得 202^0"一致。

数值精度。 (300150)≈9.4×1088\binom{300}{150} \approx 9.4 \times 10^{88},6464 位整型必然溢出, 所以组合数、概率、答案全程用 double(上限约 1.7×103081.7 \times 10^{308},精度约 15∼1715 \sim 17 位有效数字, 远优于题面要求的相对误差 10−610^{-6})。单项最大约 9.4×1088×9.4×1088≈8.8×101779.4\times10^{88} \times 9.4\times10^{88} \approx 8.8\times10^{177}, 仍在 double 范围内不会上溢。反过来,P(t)P(t) 连乘下溢成 00 时该项贡献 <10−308< 10^{-308}, 而答案下界是 11,忽略它造成的相对误差远低于 10−610^{-6}。

n=300n = 300 时循环次数是 3012≈9.06×104301^2 \approx 9.06 \times 10^4,加上 n2n^2 的递推,整体不到 2×1052\times10^5 次运算。

代码

Python 版:

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++ 版(同一算法):

cpp
/**
 * 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;
}

复杂度

  • 时间:组合数 O(n)O(n) 次递推(只用到 (n⋅)\binom{n}{\cdot} 一行,用比值递推而非帕斯卡三角), 概率数组 O(min⁡(n2,k))O(\min(n^2,k)) 次连乘,双重求和 O(n2)O(n^2)。总计 O(n2)O(n^2), n=300n = 300 时约 9×1049 \times 10^4 项,C++ 实测 9 ms、Python 实测 30 ms(限时 1000 ms)。
  • 空间:choose 与 cover_prob 各一个一维数组,O(n)O(n) 与 O(min⁡(n2,k))O(\min(n^2,k)); C++ 版用静态数组 O(n2)O(n^2),实测峰值内存 8.3 MB(限时 256 MB)。
  • 与 C++ 解法的关系:main.py 与 main.cpp 是同一算法的两种落地, 复杂度同为 O(n2)O(n^2),Python 版把帕斯卡三角换成比值递推、把二重循环收进生成器, 常数更小。本题 n⩽300n \leqslant 300,Python 实测 0.03 秒,不存在 TLE 风险。

总结

  • "恰好"很难,"指定"很容易:P(r,c)P(r,c) 需要 O(22n)O(2^{2n}) 的多维容斥, 而 P(指定的 i 行 j 列全黑)P(\text{指定的 } i \text{ 行 } j \text{ 列全黑}) 只要求覆盖的 tt 格全黑。 期望的线性性把前者换成后者,是本解法的全部杠杆。
  • 2r+c2^{r+c} 是"子集计数":2r2^r 就是"rr 个全黑行的子集个数"。 这一步把得分从"指数型的随机量"变成"对子集的指示函数之和", 从而可以逐子集取期望,不再需要先知道 rr、cc 的分布。
  • 2=1+12 = 1+1:n=1n = 1、系数为 22 的多项式看似平凡,却正好等于"所有子集求和"; 见到 2某个计数2^{\text{某个计数}} 可以条件反射地往"子集计数"上想。
  • 不管集合怎么叠,先数并集大小:ii 行 jj 列的覆盖格子数是 ni+nj−ijni+nj-ij, 交叉部分被算了两次要减掉一次。这是所有"行列并集"型题目的通用一步。
  • 精度先算量级再选类型:(300150)≈9.4×1088\binom{300}{150} \approx 9.4\times10^{88} 直接决定了 不能用整型、必须用 double;而 ∏\prod 形式的下溢因为答案有下界 11 所以无害。 这两件事不看数量级是猜不出来的。
  • 关于本题数据来源的说明:仓库内该题的 content.md 题为"一本通 1814 方格染色" (见素材源头部注释,5 轮检索未找到公开题解/AC 代码),随仓 data/ 由 data.py 生成, 题面亦可能是网络重建,出题意图与官方原题可能存在偏差。 本文的算法已用独立暴力程序核对:对 n=2,m=4n=2,m=4 穷举全部 4!×(4k)4! \times \binom{4}{k} 种 (棋盘排列 ×\times 选数集合),结果 k=2k=2 时 5/35/3、k=3k=3 时 44,与公式一致; 另在 n⩽3n \leqslant 3、m⩽13m \leqslant 13 上随机抽 (mk)\binom{m}{k} 全枚举对拍 120 组,120/120120/120 一致。 随仓 10 个数据点主解全部通过(逐字节相同),main.py 逐点输出与 .out 也完全一致。