自动搬运

查看原文

来自洛谷，原作者为

	一扶苏一 休息结束。邮箱 yifusuyi@qq.com

搬运于2025-08-24 22:11:13，当前版本为作者最后更新于2020-03-14 00:21:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

【组合计数】P5481 [BJOI2015] 糖果

Description

给定 $n ,m, k$，求满足如下条件的 $n$ 行 $m$ 列的矩形的个数：

• 矩形中都是不超过 $k$ 的正整数。
• 任取矩形中的一行，改行中的 $m$ 个数从左至右单调不下降。

两个矩形不同当且仅当至少存在一个位置不同。答案对 $p$ 取模，不保证 $p$ 是质数。

$1 \leq n, m \leq 10^5$，$1 \leq k, p \leq 10^9$。

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

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;
}