');}

组合数问题

Author Avatar
Actinoi 9月 18, 2020

NOIP2016 组合数问题

题目链接：洛谷P2822 组合数问题

打表，可以得到下面的表格

n/m 1 2 3 4 5 6
1
2
3
4 6 4
5 10 5
6 15 20 15 6

然后，很容易就能够发现这是一个杨辉三角。

接着，我们用矩阵加法来维护，实现 O(1) 的复杂度。

  1. #include <cstdio>
  2. #include <iostream>
  3. long long triangle[2100][2100], sum[2100][2100];
  4. int t, k, n, m;
  5. int min(int a, int b) {
  6.     if (a < b) return a;
  7.     return b;
  8. }
  9. void make() { //制作杨辉三角与矩阵和
  10.     triangle[1][1] = 1;
  11.     for (int i = 0; i <= 2000; i++) {
  12.         triangle[i][0] = 1;
  13.     }
  14.     for (int i = 2; i <= 2000; i++) {
  15.         for (int j = 1; j <= i; j++) {
  16.             triangle[i][j] = (triangle[i - 1][j - 1] + triangle[i - 1][j]) % k;
  17.         }
  18.     }
  19.     
  20.     for (int i = 2; i <= 2000; i++) {
  21.     //printf("%d\n", t);
  22.         for (int j = 1; j <= i; j++) {
  23.             sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
  24.             if (triangle[i][j] == 0) sum[i][j]++;
  25.         }
  26.         sum[i][i + 1] = sum[i][i];
  27.     }
  28. }
  29. int main() {
  30.     scanf("%d %d", &t, &k);
  31.     make();
  32.     for (int i = 1; i <= t; i++) {
  33.         //printf("1\n");
  34.         int n, m;
  35.         scanf("%d %d", &n, &m);
  36.         if (m > n) m = n;
  37.         printf("%lld\n", sum[n][m]);
  38.     }
  39.     return 0;
  40. }