【P2822】组合数问题【NOIP2016】

链接：https://www.luogu.org/problemnew/show/P2822

题目描述

组合数 C_n^m
​表示的是从 n 个物品中选出 m 个物品的方案数。举个例子，从 (1,2,3) 三个物品中选择两个物品可以有 (1,2),(1,3),(2,3) 这三种选择方法。根据组合数的定义，我们可以给出计算组合数 C_n^m的一般公式：
C _n^m= n!(n−m)!/n!
​其中n!=1×2×⋯×n；特别地，定义 0!=1。

小葱想知道如果给定 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：

1

输入样例#2：

2 5
4 5
6 7

输出样例#2：

0
7

说明

【样例1说明】

在所有可能的情况中，只有C₂¹ =2是2的倍数。

【数据范围】

【思路】

由于对于每次输入，虽然有很多个问题，但k是共用的，所以我们可以事先算出所有的组合数再对k取模，当模为0时即为k的倍数。
组合数可以根据公式递推求得：
C(n,m)=C(n-1,m)+C(n-1,m-1)

因为求的是一共有多少个，所以很容易就能想到前缀和。
这里用的是二维前缀和（因为i，j嘛）
二维前缀和公式：
Sum[i][j]=Sum[i-1][j]+Sum[i][j-1]-Sum[i-1][j-1]+a[i][j]
具体怎么求的画图看看就知道了，人懒不想打了QAQ

直接上代码！

//组合数问题
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2001;
//C(n,m)=C(n-1,m)+C(n-1,m-1) 
int C[MAXN][MAXN];//储存组合数答案(取模后的) 
int Sum[MAXN][MAXN];//存储有多少对(前缀和) 
int n,m,k,t;
void Calc(){
	C[1][0]=C[1][1]=1;
	for(int i=2;i<MAXN;i++){
		C[i][0]=C[i][i]=1;
		for(int j=1;j<i;j++){
			C[i][j]=C[i-1][j]+C[i-1][j-1];
			C[i][j]%=k;
		}
	}
	for(int i=2;i<MAXN;i++){
		for(int j=1;j<MAXN;j++){
			Sum[i][j]=Sum[i-1][j]+Sum[i][j-1]-Sum[i-1][j-1];
			if(j<=i&&C[i][j]==0)Sum[i][j]++;
		}
	}
}
int main(){
//	freopen("problem.in","r",stdin);
//	freopen("problem.out","w",stdout);
	scanf("%d %d",&t,&k);
	Calc();
	while(t--){
		scanf("%d %d",&n,&m);
		printf("%d\n",Sum[n][m]);
	}
	return 0;
}

（嗯，没屁放了）