CWOI S C0224 A 姨

题意使用 openssl enc -aes256 -pbkdf2 加密。

U2FsdGVkX19KNu7iZOcGm3sJYfaIorxIQzvuZlHdG4ROdc8IigY8rD+z5BrunObE
QfbqsMr8ZzHv6EMKUfnB8OOeP2S8kCzkFg9XTFDIIbDlLHoNFqyCE5XP81ychReS
cdZP9WOhwh/usiOe3bM6fk8wPdEKe6qwGn1nKkJuqZ8Pi99RHVQKDb83+BNX3+Ch
i9OPRKN73Jc1rfpUnrq1pSMhqHeeuBGFVSpiUDMpxtmy6s20eEpJIS5XWJN+YfpU
ImJhhrOIBPVwzbpyzsadkuI8VlkAGEcMD/DKIzjtD4NrVL6tSrbPTqw2PFhm9kQ6
gvRosq/xbNYXkqZR1NfH+NsySbhORQHhaqdAxDYmduBi7FZXoChSvHYTut8dl0yR
z/Ux2EQv3xnIAWUPGhVZMSDg7h2M2Q2LDmNIHGn4MIJ1kguHKq8zSx0gIc69DsEI
KrruRF+xIFXoSbXX/P3wzP4B9Dele6mauGHt1f6iHHLj4ccaH3Dd642ZUPfLLJAo
WbZs5lqFcyXh4o0x0+Uk1H/Dpi1ivgKTwYCYfCxMVXjHHrP3NtdC9bctgGXMyyl8
TKuv4ypytf2tUzSzooomrMnnWpl3LL9eEBv73pjFuM/zmYtx6cy2C8u+v+uZZK2R
eAr8du9F+Be0oqxXEEWBtQ==

解析

大便题目，不取模是什么 sb 操作。

分数的 $2^{R+C}$ 可以看作染黑的 $R$ 行 $C$ 列中选择一个子集的所有方案。

枚举有 $i$ 行 $j$ 列被染黑，对答案的贡献就是：

$$\frac{\binom{n}{i}\binom{n}{j}\binom{m-t(i, j)}{k-t(i, j)}}{\binom{m}{k}}$$

其中 $t(i, j) = i \times n + j \times n - i \times j$，即是染 $i$ 行 $j$ 列需要染黑的格子数量。

注意到 $\binom{m-t(i, j)}{k-t(i, j)} = \binom{m-t(i, j)}{m-k}$，可以预处理出来。

可能需要高精度。

from decimal import *
import functools

n, m, k = map(int, input().split())

fact = [1]
for i in range(1, n + 1):
    fact.append(fact[-1] * i)

@functools.cache
def binom(n, m):
    if m < 0 or m > n:
        return 0
    return fact[n] // fact[m] // fact[n - m]

@functools.cache
def t(i, j):
    return i * n + j * n - i * j

f = []

for i in range(m + 1):
    if i < m - k:
        f.append(0)
    elif i == m - k:
        f.append(1)
    else:
        f.append(f[i - 1] * i // (i - m + k))

s = ((f[m - t(i, j)] * binom(n, i) * binom(n, j) for i in
    range(n + 1)) for j in range(n + 1))

ans = sum((sum(i) for i in s))

tot = f[m]

getcontext().prec = 1000

ans = Decimal(ans) / Decimal(tot)

if ans >= pow(10, 99):
    print(pow(10, 99))
else:
    print(ans)

关于相对误差

如果题目要求你的答案 $a$ 与标准答案 $b$ 的相对误差不超过 $\epsilon$，实际上是要求 $\frac{|a - b|}{b} \le \epsilon$，写 checker 时一定要注意！