假日团队赛34——A组合数问题

网址：https://ac.nowcoder.com/acm/contest/3888/A

题目描述

组合数表示的是从 n 个物品中选出 m 个物品的方案数。举个例子，从 (1, 2, 3) 三个物品中选择两个物品可以有 (1, 2)，(1, 3)，(2, 3) 这三种选择方法。
根据组合数的定义，我们可以给出计算组合数的一般公式：
C(n,m) = {n!}/{m!(n - m)!}
小葱想知道如果给定 n，m 和 k，对于所有的 0 ≤ i ≤ n， 0 ≤ j ≤ min(i,m) 有多少对 (i, j) 满足C(i.j)是 k 的倍数。

输入描述:

第一行有两个整数 t，k，其中 t 代表该测试点总共有多少组测试数据，k 的意义见 「题目描述」。
接下来 t 行每行两个整数 n，m，其中 n，m 的意义见「题目描述」。

输出描述:

t 行，每行一个整数代表对于所有的 0 ≤ i ≤ n， 0 ≤ j ≤ min(i,m) 有多少对 (i, j) 满足C（i，j）是 k 的倍数。

示例1

输入
1 2
3 3
输出
1

示例2

输入
2 5
4 5
6 7
输出
0
7
说明
在所有可能的情况中，只有C(2,1)=2是 2 的倍数。

备注:

3 ≤ n, m ≤ 2000, 2 ≤ k ≤ 21, 1 ≤ t ≤ 10000

题解：

对于这种每次样例比较多，（t<=10000）,一般采用预处理的方法来进行研究计算
计算从c[i][j]是否是k的倍数，只需计算从c[i][j]%=k是否为0，因为c[i][j]=c[i-1][j]+c[i-1][j-1],（注：从i个物品中挑选出j个物品=第i个物品没有被选中，从剩下i-1中选出j个物品+第i个物品被选中，从剩下的i-1个物品中选出j-1个物品），所以在每一步计算c[i][j]%=k,并不影响后面组合数的计算，因为后面组合数等于其前面某两个组合数的和，而对于求和来说，先求余后相加，与先相加后求余的结果相等。

AC代码：

#include<iostream>
using namespace std;
int c[2100][2100]={0};//排列组合除以k的结果 
int n,m,t,k;
void Init(){//初始化，预处理，利用了c[i][j]=c[i-1][j]+c[i-1][j-1]; 
    c[0][0]=0,c[1][1]=1;
    for(int i=1;i<=2000;i++){
        for(int j=0;j<=i;j++){
            if(j==0||i==j) c[i][j]=1,c[i][j]%=k;
            else {
                c[i][j]=c[i-1][j]+c[i-1][j-1];
                c[i][j]%=k;
            }
        }
    }
}
int main (){
    cin>>t>>k;
    Init(); 
    for(int i=1;i<=2000;i++){//c[i][j]:表示原先的c[i][0]到c[i][j]一共存在多少个0 
        for(int j=0;j<=i;j++){
            if(!c[i][j]){
                if(j) c[i][j]=c[i][j-1]+1;
                else c[i][j]=1;
            }
            else {
                if(j) c[i][j]=c[i][j-1];
                else c[i][j]=0;
            }
        }

    }
    while(t--){
        cin>>n>>m;
        int sum=0;
        for(int i=1;i<=n;i++){
            sum+=c[i][min(i,m)];
        }
        cout<<sum<<endl;
    }
    return 0;
}

打卡第6天，继续加油啊。虽然牛客练习赛59——F小松鼠吃松果，即便看了题解依旧没能弄明白，但请相信自己，你是最棒的，只要继续付出，终究你会慢慢的变强！！！加油，送给现在的自己。