网址：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;
}
京公网安备 11010502036488号