洛谷P2822组合数问题

题目描述

解题思路

由于 0 <= i <= n, 0 <= j <= min(i,m),我们要求出每一组 (i, j) 的组合数，判断其是否能被 k 整除，能则 ans++,否则 ans 不变。如果我们每求一次 (i, j) 就求一次组合数，那么一定会超时。这里有一种递推的方式求组合数，根据公式 C(n,m) = C(n-1, m) + C(n-1, m-1)，我们开一个二维数组 C[N][N],C[n][m]存的是 (n,m) 的组合数
n\m 0 1 2 3 4
0 1
1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 3 1
不难发现，这是个杨辉三角，第 i 行 j 列对应的值刚好是组合数(i,j)的值，由于递推的结果可能很大，我们对每一个C[i][j]都要取模，这里直接模 k，如果 C[i][j] == 0 则说明，C[i][j] 能被 k 整除。所以对给出的 n,m,我们只需要统计，所有满足，0 <= i <= n,0 <= j <= min(i,m)的(i,j)组合中，C[i][j] == 0的个数。可以直接遍历求，但是还是会超时，所以我们再开一个S[N][N]的数组，用来做二维前缀和的存储单元。

Input

1 2
3 3

Output

1

Input

2 5
4 5
6 7

Output

0
7

AC代码

#include <iostream>
using namespace std;

const int N = 2010;

int C[N][N],s[N][N];
int t,k,n,m,ans;

void build(){
    C[1][1] = 1;
    for(int i = 0; i <= 2000; i++) C[i][0] = 1;
    for(int i = 2; i <= 2000; i++){
        for(int j = 1; j <= 2000; j++){
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % k;
        }
    }
    for(int i = 0; i <= n; i++){
        s[i][0] += s[i-1][0];
        if(C[i][0] % k == 0) s[i][0] ++; //为什么不直接判断等于 0，因为我怕 k 可以等于 1
    }
    s[0][1] = s[0][0];
    for(int i = 1; i <= 2000; i++){
        for(int j = 1; j <= i; j++){
            s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1]; //加上 加左 减左上，求二维前缀和
            if(C[i][j] % k == 0) s[i][j] ++;
        }
        s[i][i+1]=s[i][i]; //方便计算下一层的最后一个
    }
}

int main(){
    cin >> t >> k;
    build();
    while(t--){
        cin >> n >> m;
        if(m > n) m = n; //一个坑： m 可能比 n 大
        cout << s[n][m] << endl;
    }
    return 0;
}