思路与算法

设完成行集合大小R、列集合大小C。把2^(R+C)展开为所有行列子集“均完成”的指示量之和。选r行c列需涂黑q=n(r+c)-rc格，概率为(k)_q/(m)_q。对r,c累加C(n,r)C(n,c)乘该概率，超过1e99时截为1e99。

正确性说明

每一行或列可选或不选，展开恰好有2^(R+C)个已完成子集。期望线性性不要求独立。棋盘格数字互异，固定q格全在均匀k数字样本中的概率等价不放回连续乘积，q>k为0。按行列数量分类后的组合系数精确计重，因此总和为所求期望。

复杂度

组合数O(n)，概率递推O(n²)，双循环O(n²)，总O(n²)时间与空间；概率表初始化O(n²)，使用long double中间值。只预存一维概率时组合表也是一维。

易错点

同时完成的行列在交点重合，必须减rc，不能当独立事件相乘。输出按相对误差1e-6配置原生特判；NaN、无穷和额外输出拒绝。公开n=1样例也纳入协议，最终结果才截上限。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    vector<long double> bin(n + 1, 1), prob(n * n + 1);
    for (int i = 1; i <= n; i++)
        bin[i] = bin[i - 1] * (n - i + 1) / i;
    prob[0] = 1;
    for (int i = 1; i <= min(k, n * n); i++)
        prob[i] = prob[i - 1] * (k - i + 1) / (m - i + 1);
    long double ans = 0;
    for (int r = 0; r <= n; r++)
        for (int c = 0; c <= n; c++)
            ans += bin[r] * bin[c] * prob[n * (r + c) - r * c];
    cout << setprecision(18) << scientific << min(ans, 1e99L) << '\n';
}