NOIP 2016 D2T1 组合数问题

胡雨菲菲

题目描述
组合数 Cnm表示的是从 n 个物品中选出 m 个物品的方案数。

小葱想知道如果给定 n,m 和 k ，对于所有的 0 <= i <= n , 0 <= j <= min(i, m) , 有多少对 (i,j) 满足 Cij 是 k 的倍数。

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

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

输出格式：
共 t 行，每行一个整数代表所有的  0 <= i <= n , 0 <= j <= min(i, m) 中有多少对 (i,j)(i,j) 满足 Cij 是 k 的倍数。

输入输出样例
输入样例#1：
1 2
3 3
输出样例#1：
1
输入样例#2：
2 5
4 5
6 7
输出样例#2：
0
7

胡雨菲菲

1. #include <cstdio>
   
2. const int N = 2010;
   
3. 
   
4. int C[N][N], ans[N][N], mo;
   
5. 
   
6. int main() {
   
7.     int T;
   
8.     scanf("%d%d", &T, &mo);
   
9.     C[0][0] = 1;
   
10.     for(int i = 1; i < N; i++) {
    
11.         C[i][0] = 1;
    
12.         for(int j = 0; j <= i; j++) {
    
13.             C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mo;
    
14.         }
    
15.     }
    
16.    
    
17.     for(int i = 0; i < N; i++) {
    
18.         for(int j = 0; j <= i; j++) {
    
19.             C[i][j] = C[i][j] ? 0 : 1;
    
20.         }
    
21.     }
    
22.    
    
23.     ans[0][0] = C[0][0];
    
24.     for(int i = 1; i < N; i++) {
    
25.         ans[i][0] = ans[i - 1][0] + C[i][0];
    
26.         for(int j = 1; j < N; j++) {
    
27.             ans[i][j] = ans[i - 1][j] + ans[i][j - 1] - ans[i - 1][j - 1] + C[i][j];
    
28.         }
    
29.     }
    
30. 
    
31.     while(T--) {
    
32.         int m, n;
    
33.         scanf("%d%d", &n, &m);
    
34.         printf("%d\n", ans[n][m]);
    
35.     }
    
36.     return 0;
    
37. }
    

复制代码