题解 P9475【考试】
0x3F
·
·
题解
由期望的线性性可知，总分的期望等于每一道题得分的期望之和。
我们可以把题分为 5 类：
- 题号对应，个数为 C_
{eq}。
- 题号不对应，应该填单选题，实际填单选题，个数为 C_{11}。
- 题号不对应，应该填单选题，实际填多选题，个数为 C_{12}。
- 题号不对应，应该填多选题，实际填单选题，个数为 C_{21}。
- 题号不对应，应该填多选题，实际填多选题，个数为 C_{22}。
同时，这 5 类题单个对答案的贡献分别为 S_{eq},S_{11},S_{12},S_{21},S_{22}。
答案为：C_{eq}S_{eq}+C_{11}S_{11}+C_{12}S_{12}+C_{21}S_{21}+C_{22}S_{22}。
首先，求 C_{eq},C_{11},C_{12},C_{21},C_{22} 的值。
假设第 i 行第 j 列的题的坐标为 (i,j)，那么横向排列时其题号为 (i-1)m+j，纵向排列时其题号为 (j-1)n+i。
如果不考虑题号是否对应，那么应该填单选题，实际填单选题的个数 C_{11}' 就是满足 (i-1)m+j\le k,(j-1)n+i\le k 的 (i,j) 的数量。
满足 (i-1)m+j\le k 的区域可以分拆为两个矩形 R_1=[1,\lfloor\frac{k}{m}\rfloor]\times[1,m] 和 R_2=[\lfloor\frac{k}{m}\rfloor+1,\lfloor\frac{k}{m}\rfloor+1] \times [1,k\bmod m] 的不交并，如图所示。
满足 (j-1)n+i\le k 的区域也可以分拆成两个矩形 R_3,R_4。
可以求出 C_{11}'=\vert(R_1 \cup R_2) \cap (R_3 \cup R_4)\vert = \vert R_1\cap R_3\vert + \vert R_1\cap R_4\vert + \vert R_2\cap R_3\vert + \vert R_2\cap R_4\vert。
而矩形的交的计算是非常简单的。
同时，显然有 C_{12}=k-C_{11}',C_{21}=k-C_{11}',C_{22}'=nm-C_{11}'-C_{12}-C_{21}。
接下来考虑题号对应的情况。题号对应时，有 (i-1)m+j=(j-1)n+i，即 (i-1)(m-1)=(j-1)(n-1)。
记 \gcd(n-1,m-1)=g，则 \gcd(\frac{n-1}{g},\frac{m-1}{g})=1，
故 (i-1)\times\frac{m-1}{g}=(j-1)\times\frac{n-1}{g}，当且仅当 i-1=\frac{t(n-1)}{g},j-1=\frac{t(m-1)}{g}，其中 t\in\mathbb{Z} 且 0\le t\le g。
此时，题号为 (i-1)m+j=(j-1)n+i=\frac{t(nm-1)}{g}+1。
当题号对应的这题为单选题时，有 \frac{t(nm-1)}{g}+1\le k，即 t\le\lfloor\frac{(k-1)g}{nm-1}\rfloor，因此 C_{11}=C_{11}'-(\lfloor\frac{(k-1)g}{nm-1}\rfloor+1)。同理，C_{22}=C_{22}'-(\lfloor\frac{(nm-k-1)g}{nm-1}\rfloor+1)。由于 t 的取值共有 g+1 种，故 C_{eq}=g+1。
注意特判 n=m=1。
接下来，求 S_{eq},S_{11},S_{12},S_{21},S_{22} 的值。
$S_{11}$：显然为 $\frac{1}{c}$。
$S_{12}$：显然为 $0$。
$S_{21}$：为 $\frac{1}{c}$。假设多选题有 $a$ 个选项，则有 $\frac{a}{c}$ 的概率得 $\frac{1}{a}$ 分，无论多选题的选项是怎样的，得分期望都为 $\frac{1}{c}$。
$S_{22}$：一道多选题的选项共有 $2^c-c-2$ 种可能，因此符合条件的选项 $(A,B)$ 共有 $(2^c-c-2)^2$ 种。考虑计算这些 $(A,B)$ 的得分之和。
假设 $\vert A\vert=i,\vert B\vert=j$，$A$ 有 $\mathrm{C}_{c}^{i}$ 种选法，由于 $B\sube A$，故 $B$ 有 $\mathrm{C}_{i}^{j}$ 种选法，对答案的贡献为 $\frac{j}{i}$。同时，有 $2\le i\le c-1,2\le j\le i$ 的限制。因此，得分之和为：
$$\sum_{i=2}^{c-1}\sum_{j=2}^{i}\mathrm{C}_{c}^{i}\mathrm{C}_{i}^{j}\frac{j}{i}$$
$$=\sum_{i=2}^{c-1}\frac{\mathrm{C}_{c}^{i}}{i}\sum_{j=2}^{i}j\mathrm{C}_{i}^{j}$$
由二项式定理，$(x+y)^{n}=\mathrm{C}_{n}^{0}y^{n}+\mathrm{C}_{n}^{1}xy^{n-1}+\cdots+\mathrm{C}_{n}^{n}x^n$，令 $y\gets1$，得：
$$(x+1)^{n}=\mathrm{C}_{n}^{0}+\mathrm{C}_{n}^{1}x+\mathrm{C}_{n}^{2}x^2+\mathrm{C}_{n}^{3}x^3+\cdots+\mathrm{C}_{n}^{n}x^n(\star)$$
$(\star)$ 两边关于 $x$ 求导，得：
$$n(x+1)^{n-1}=\mathrm{C}_{n}^{1}+2\mathrm{C}_{n}^{2}x+3\mathrm{C}_{n}^{3}x^2+\cdots+n\mathrm{C}_{n}^{n}x^{n-1}$$
令 $x\gets 1,n\gets i$ 得：
$$i2^{i-1}=\mathrm{C}_{i}^{1}+2\mathrm{C}_{i}^{2}+3\mathrm{C}_{i}^{3}+\cdots+i\mathrm{C}_{i}^{i}$$
移项得：
$$2\mathrm{C}_{i}^{2}+3\mathrm{C}_{i}^{3}+\cdots+i\mathrm{C}_{i}^{i}=i2^{i-1}-\mathrm{C}_{i}^{1}=i(2^{i-1}-1)$$
故原式可化简为：
$$\sum_{i=2}^{c-1}\frac{\mathrm{C}_{c}^{i}}{i}\times i(2^{i-1}-1)$$
$$=\frac{1}{2}\sum_{i=2}^{c-1}2^{i}\mathrm{C}_{c}^{i}-\sum_{i=2}^{c-1}\mathrm{C}_{c}^{i}$$
$(\star)$ 中，令 $x\gets 1,n\gets c$ 得：
$$2^c=\mathrm{C}_{c}^{0}+\mathrm{C}_{c}^{1}+\mathrm{C}_{c}^{2}+\mathrm{C}_{c}^{3}+\cdots+\mathrm{C}_{c}^{c-1}+\mathrm{C}_{c}^{c}$$
移项得：
$$\mathrm{C}_{c}^{2}+\mathrm{C}_{c}^{3}+\cdots+\mathrm{C}_{c}^{c-1}=2^c-\mathrm{C}_{c}^{0}-\mathrm{C}_{c}^{1}-\mathrm{C}_{c}^{c}=2^c-c-2$$
$(\star)$ 中，令 $x\gets 2,n\gets c$ 得：
$$3^c=\mathrm{C}_{c}^{0}+2\mathrm{C}_{c}^{1}+4\mathrm{C}_{c}^{2}+8\mathrm{C}_{c}^{3}+\cdots+2^{c-1}\mathrm{C}_{c}^{c-1}+2^{c}\mathrm{C}_{c}^{c}$$
移项得：
$$4\mathrm{C}_{c}^{2}+8\mathrm{C}_{c}^{3}+\cdots+2^{c-1}\mathrm{C}_{c}^{c-1}=3^c-\mathrm{C}_{c}^{0}-2\mathrm{C}_{c}^{1}-2^{c}\mathrm{C}_{c}^{c}=3^c-2^c-2c-1$$
故原式可化简为：
$$\frac{3^c-2^c-2c-1}{2}-(2^c-c-2)$$
$$=\frac{3^c-3\times2^c+3}{2}$$
故 $S_{22}=\frac{3^c-3\times2^c+3}{2(2^c-c-2)^2}$。
时间复杂度为 $O(\log n+\log m+\log c)$。
代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
const int p = 1e9 + 7;
inline int qpow(int a, long long b) {
int s = 1;
while (b) {
if ((b & 1LL)) s = (long long)s * a % p;
a = (long long)a * a % p;
(b >>= 1LL);
}
return s;
}
int n, m, c;
long long nm, k;
long long ceq, c11, c12, c21, c22;
int seq, s11, s12, s21, s22;
int ans;
int main() {
cin >> n >> m >> k >> c;
nm = (long long)n * m;
c11 = (k/m) * (k/n) + min(k/n, k%m) + min(k%n, k/m) + (k/m < k%n && k/n <= k%m);
c12 = k - c11;
c21 = k - c11;
c22 = nm - c11 - c12 - c21;
int g = __gcd(n-1, m-1);
long long step = ((g) ? ((nm - 1) / g) : (1LL));
ceq = g+1;
c11 -= (step + k - 1) / step;
c22 -= (step + nm - k - 1) / step;
seq = 1;
s11 = qpow(c, p-2);
s12 = 0;
s21 = qpow(c, p-2);
s22 = ((((long long)qpow(3, c) - 3LL * qpow(2, c) + 3) % p + p) % p * qpow(2, p-2) % p) * qpow(((qpow(2, c) - c - 2) % p + p) % p, p-3) % p;
ans = (ans + ceq % p * seq) % p;
ans = (ans + c11 % p * s11) % p;
ans = (ans + c12 % p * s12) % p;
ans = (ans + c21 % p * s21) % p;
ans = (ans + c22 % p * s22) % p;
cout << ans << endl;
return 0;
}
```