题解 P5481 【[BJOI2015] 糖果】
一扶苏一
·
·
题解
【组合计数】P5481 [BJOI2015] 糖果
Description
给定 n ,m, k，求满足如下条件的 n 行 m 列的矩形的个数：
- 矩形中都是不超过 k 的正整数。
- 任取矩形中的一行，改行中的 m 个数从左至右单调不下降。
两个矩形不同当且仅当至少存在一个位置不同。答案对 p 取模，不保证 p 是质数。
### Solution
计数杀我。
首先注意到每一行都是独立的，因此我们只需要求出长度为 $m$ 的值域为 $[1, k]$ 的不下降序列的方案数 $s$，在其中任选 $n$ 个进行排列都能得到一种新的矩形。总方案数为 $A_{s}^n$，我们考虑求 $s$。
注意到因为序列是单调不降的，所以我们只需要确定每个数在序列中出现了几次，就可以唯一确定这个序列。这个问题等价于下面这个问题：
有 $m$ 个小球和 $k$ 个盒子，小球全部相同而盒子互不相同，盒子可以为空，求将所有小球放入盒子的方案数。
事实上，一个盒子 $a$ 里面有 $b$ 个球对应着这个序列里有 $b$ 个值为 $a$ 的数。
这是一个经典问题，盒子可以为空的限制看起来比较烦人，我们考虑先给每个盒子都扔进去一个小球，也即求 $(m + k)$ 个小球扔进 $k$ 个盒子且盒子不能为空的方案数。
考虑新问题（即不能为空）的每种方案，从每个盒子中都拿掉一个球，一定唯一对应着原问题（可以为空）的一种方案，而对于原问题的一个方案，向每个盒子都扔进去一个球，得到的方案一定唯一对应着新问题对应该方案的方案。因此这两个问题的方案是一一对应的。
我们可以递推求解新问题：设 $f_{i, j}$ 是放了 $i$ 个球，放在了前 $j$ 个盒子里的方案数。能转移到该状态的只有两种情况：$i$ 放到一个新盒子，$i$ 放到一个已经有球的盒子。因此
$$f_{i, j} = f_{i - 1, j - 1} + f_{i - 1, j}$$
初始条件为 $f_{1, 1} = 1$。
注意到这个递推式与组合数递推式（pascal 公式）**完 全 一 致**，因此所求即为 $C_{m + k}^k$？
注意到这个三角形与杨辉三角不一致的地方在于 $f_{0, 1} = 0$，也即相当于三角形整体向右向下移动各了一个单位，所以所求实际上应该是 $C_{m + k - 1}^{k - 1}$。
$k$ 太大了不好算，根据杨辉三角的对称性，所求即为 $C_{m + k - 1}^{m + k - 1 - k + 1} = C_{m + k - 1}^m$。
下一个问题是，我们求出来的 $s$ 是作为 $A$ 的下角标存在的，而这个数取模以后似乎就丧失了直观组合意义。
考虑
$$A_{s}^{n} = \frac{s!}{(s - n)!} = s \times (s - 1)\times \dots \times(s - n + 1) = \prod\limits_{i = 0}^{n - 1} (s - i)$$
注意到，要求 $A_{s}^n$ 在模 $p$ 下结果，由于结果是一个连乘式，所以是可以直接对 $s$ 进行取模的，只需要计算模意义下 $(s - i)$ 的值即可。
现在考虑求 $C_{m + k - 1}^m$。由于 $p$ 不是质数，无法直接求阶乘逆元，考虑计算过程本身
$$C_{m + k - 1}^m = \frac{(m + k - 1)!}{m! (k - 1)!}$$
注意到 $m$ 非常小，而 $\frac{(m + k - 1)!}{(k - 1)!} = \prod\limits_{i = 0}^{m - 1} k + i$，我们考虑直接对 $m!$ 分解质因数，然后从连乘式中逐项除掉对应的质因子即可。
时间复杂度 $O(m \log m + n)$。
### Code
```cpp
const int maxn = 100005;
int n, m, k, p;
int calc();
int main() {
freopen("1.in", "r", stdin);
qr(n); qr(m); qr(k); qr(p);
if (p == 1) {
puts("0");
return 0;
}
qw(calc(), '\n', true);
return 0;
}
int pcnt;
int prm[maxn], pre[maxn];
bool np[maxn];
void Getp(const int x) {
for (int i = 2; i <= x; ++i) {
if (!np[i]) {
pre[prm[++pcnt] = i] = i;
}
for (int j = 1, k; j <= pcnt; ++j) if ((k = i * prm[j]) <= x) {
np[k] = true;
pre[k] = prm[j];
if ((i % prm[j]) == 0) {
break;
}
} else {
break;
}
}
}
int a[maxn], b[maxn];
int calc() {
Getp(m);
for (int i = 0; i < m; ++i) {
a[i] = i + k;
int t = i + 1;
while (t != 1) {
++b[pre[t]];
t /= pre[t];
}
}
int dk = k - 1;
for (int i = 2; i <= m; ++i) if (!np[i]) {
for (int j = (dk / i + 1) * i - k; b[i]; j += i) while ((a[j] % i) == 0) {
a[j] /= i;
if (--b[i] == 0) break;
}
}
ll s = 1, ret = 1;
for (int i = 0; i < m; ++i) (s *= a[i]) %= p;
for (int i = 0; i < n; ++i) {
(ret *= (s - i + p)) %= p;
}
return ret;
}
```