P2822 [NOIP 2016 提高组] 组合数问题

题目背景

NOIP2016 提高组 D2T1

题目描述

组合数 $\binom{n}{m}$ 表示的是从 $n$ 个物品中选出 $m$ 个物品的方案数。举个例子，从 $(1,2,3)$ 三个物品中选择两个物品可以有 $(1,2),(1,3),(2,3)$ 这三种选择方法。根据组合数的定义，我们可以给出计算组合数 $\binom{n}{m}$ 的一般公式：

$$\binom{n}{m}=\frac{n!}{m!(n-m)!}$$

其中 $n!=1\times2\times\cdots\times n$；特别地，定义 $0!=1$。

小葱想知道如果给定 $n,m$ 和 $k$，对于所有的 $0\leq i\leq n,0\leq j\leq \min \left ( i, m \right )$ 有多少对 $(i,j)$ 满足 $k\mid\binom{i}{j}$。

输入格式

第一行有两个整数 $t,k$，其中 $t$ 代表该测试点总共有多少组测试数据，$k$ 的意义见问题描述。

接下来 $t$ 行每行两个整数 $n,m$，其中 $n,m$ 的意义见问题描述。

输出格式

共 $t$ 行，每行一个整数代表所有的 $0\leq i\leq n,0\leq j\leq \min \left ( i, m \right )$ 中有多少对 $(i,j)$ 满足 $k\mid\binom{i}{j}$。

输入输出样例 #1

输入 #1

1
2
1 2
3 3

输出 #1

1
1

输入输出样例 #2

输入 #2

1
2
3
2 5
4 5
6 7

输出 #2

1
2
0
7

说明/提示

【样例1说明】

在所有可能的情况中，只有 $\binom{2}{1} = 2$ 一种情况是 $2$ 的倍数。

【子任务】

  • 对于全部的测试点，保证 $0 \leq n, m \leq 2 \times 10^3$，$1 \leq t \leq 10^4$。

题解

代码示例与注释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2003;
ll n, m, t, k;
// 杨辉三角：f[i][j] = f[i-1][j-1] + f[i-1][j] (组合数公式)
// 二维数组的前缀和优化
ll C[MAXN][MAXN]; // 存模k的余数
ll ans[MAXN][MAXN];
int main() {
    scanf("%d%d", &t, &k);
    C[0][0] = 1;
    for(int i=0; i<MAXN; i++) {
        for(int j=0; j<=i; j++) {
            if(j==0 || j == i) {
                C[i][j] = 1;
            }
            else C[i][j] = (C[i-1][j-1] + C[i-1][j]) % k; 
            // 如果mod k 余0 就储存到答案数组中
            if(i>=1 && j>=1) {
                ans[i][j] = ans[i-1][j] + ans[i][j-1] - ans[i-1][j-1] + (C[i][j] == 0);
            }
            else if(i==0 && j>0) ans[i][j] = ans[i][j-1] + (C[i][j] == 0);
            else if(i>0&&j==0) ans[i][j] = ans[i-1][j] + (C[i][j] == 0);
            if(j == i) ans[i][i+1] = ans[i][i]; // 处理边界
            // 由于ans数组初始化为0了 如果不处理这一步边界 之后算ans[i+1][i+1]时加上的ans[i][i+1]会等于0
            // 这样会遗失统计 故要处理一下边界
            // 画出三角图形易知这样处理符合实际情况
        }
    }
    for(int i=0; i<t; i++) {
        scanf("%d%d", &n, &m);
        printf("%d\n", ans[n][min(n, m)]);
    }
    return 0;
}

注意

  • 本题使用了杨辉三角递推地计算组合数
  • 还使用了二维前缀和优化了求解过程
  • 注意本题要求的是可以被k整除的情况 答案mod k即可