[Noip2017]组合数问题

一.前言

组合数学没学好阿巴阿巴……题目链接

二.思路

首先给一个结论：杨辉三角和组合数的关系是密不可分的。这两个就是一个东西其实。先来康康一个很显而易见的数学公式。

[C_m^n=C_{m}^{n-1}+C_{m-1}^{n-1} ]

大概，还是很容易理解的，吧……稍作解释就是。

在 n 个数中选 m 个做组合的情况可以从在前 n-1 个数中就选出 m 个和在前 n-1个数中选出 m-1 个转移过来（后一种是第 n 个塞进去）

然后稍加观察，若是把 n 当作行， m 当作列的话，就是杨辉三角。换而言之，(C^i_j) 为杨辉三角的第 i 行，第 j 列的值。

然后我们再看问题，求的是 k 的倍数的个数，也就是 (\%k=0) 的个数，这里将询问离线，预处理直接(O(1))解决询问。所以预处理一个基于杨辉三角的前缀和数组 (sum[n][m]) 表示答案。转移方程为

[sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1] ]

然后加一个当前值是不是 (\%k=0) 判断就ok。

关于转移方程，可以具体手推，这里给出一个抽象理解。（今天手比较抖）

框住的表示这一部分的前缀和，现在是在求红框。灰色是重复部分。

但是这是常规的杨辉三角，计算机里面的杨辉三角，稍微有点点不同，是个方的，所以画图为

大概是这种感觉，然后可以发现篮框右下角是空点，实际上空点的值应该是空点左边的值，为了方便计算就有一个(sum[i][i+1]=sum[i][i]),后面推就没有问题了。

三.CODE

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<fstream>
#include<cmath>
using namespace std;
int read(){
	char ch=getchar();
	int res=0,f=1;
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())res=res*10+(ch-'0');
	return res*f;
}
int t,k,n,m;
int f[2005][2005],sum[2005][2005];
int main(){
	t=read();k=read();
	for(int i=0;i<=2004;++i)f[i][i]=f[i][0]=1;
	for(int i=1;i<=2004;++i){
		for(int j=1;j<=i;++j){
			f[i][j]=(f[i-1][j]+f[i-1][j-1])%k;//一直膜就对了
			sum[i][j]=(sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]);
			if(!f[i][j])sum[i][j]++;
		}
		sum[i][i+1]=sum[i][i];//比较关键的一步
	}
	while(t--){
		n=read();m=read();
		cout<<sum[n][min(n,m)]<<endl;
	}
	return 0;
}