距离上一次写题解已经过了十个甚至九个月了，中间的课是都不会啊！！！（恼）

免责声明

本篇题解所写内容均为个人想法，并不代表且可能完全与代老师的标准思路、答案无关。若遇到此种情况，以英明神武帅气的代老师的代码为准。本人代码仅供参考。

组合数问题

一：组合数处理

如题目所说，组合数求解是有最基本的公式的。但是这个公式上下都是阶乘，一次次算肯定十分的浪费时间。因此需要考虑到一定的优化。

观察题目数据范围可以发现，n只有2000！！！多么的小啊！！！！因此我们肯定可以把全部的组合数算出来，然后每次求解的时候再考虑求和问题。直接上二维数组记录一下C[i][j]。

ps:我一开始以为开longlong空间不够，故补上计算结果:

2000 * 2000 * 8 / 1024 / 1024 = 30.517MB

显而易见的，可以利用数论中的杨辉三角的递推式来求解。每次都利用之前求过的C来求解本次的。由于公式的markdown对于本蒟蒻十分的难写，故给出wiki传送门：

组合数学 | 33Wiki (33dai.cn)

线性求出后，每次用n²的复杂度统计，整体复杂度是O(n²t)，10¹⁰级别，肯定过不了。因此我们需要考虑再次优化求和时候的平方级复杂度。

当然，如果不优化，也有70pts，加个取模操作90pts。

二：前缀和优化

考虑每次求和做的事情，其实就是在杨辉三角中找出当前这个点左上角那一部分的 C[i][j]%k==0 的数字数量只和。我们可以在脑子里构建一个新的二维bool数组，如果是当前位置是1表示这个地方的C可以被整除，为最终的结果提供1的贡献。所以最终就是将这样的一个表进行二维前缀和（求和）操作。将每次询问复杂度优化为O(1)，故最终复杂度是O(n²)。

当然，这个表其实并不需要真的建出来。它的功能可以和前缀和的数组相结合。假设前缀和数组是d，则可以得到以下的公式：

d[i][j]=d[i-1][j]+d[i][j-1]-d[i-1][j-1]+(c[i][j]==0);

如图所示，相信可以给忘记了二维前缀和的同学们（包括我）提供一些想法。轻轻敲醒沉睡的心灵

左图为取模k（假设k=5）时的杨辉三角。右图为根据贡献画出来的树。如果我们要求白框位置为右下角的一整个图形面积，就是 上方红框+左侧红框-左上方篮框 的1的总数量，加上自己这个位置是否是1，因此就是上方的公式。

三：上代码！

部分小细节在代码中注释给出，最终就可以得到如下代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=2005;
int t,k,n,m;
int c[MAXN][MAXN],d[MAXN][MAXN];
void C_init(int x,int y)
{
	c[0][0]=1; //最上方的数字初始化为0 
	for(int i=1;i<=x;i++)
	{
		c[i][0]=1;
		for(int j=1;j<=min(i,y);j++)
			c[i][j]=(c[i-1][j]%k+c[i-1][j-1]%k)%k;//公式 
		//每次求的时候就取模，更加方便 
	}
	return;
}
void qzh(int x,int y)
{
	for(int i=0;i<=x;i++)
	{
		for(int j=0;j<min(i,y);j++)
		{
			if(i==0&&j==0)//如果是左上角的位置，只需要加自己 
				d[i][j]=(c[i][j]==0);
			else if(i==0)//如果是第0行，i轴不变 
				d[i][j]=d[i][j-1]+(c[i][j]==0);
			else if(j==0)//如果是第0列，j轴不变，只加i轴 
				d[i][j]=d[i-1][j]+(c[i][j]==0);
			else//正常的前缀和公式 
				d[i][j]=d[i-1][j]+d[i][j-1]-d[i-1][j-1]+(c[i][j]==0);
		}
		d[i][min(i,y)]=d[i][min(i,y)-1]+(c[i][min(i,y)]==0);
		//特殊判断，将最右侧的值赋为左侧的值加上自己
		//因为最右侧的实际上就等于左侧的矩形，但是它上方矩形的数值为0
		//所以直接加的答案会错误，需要特殊处理 
	}
	return;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>t>>k;
	C_init(2000,2000); //线性求组合数函数 
	qzh(2000,2000); //二维前缀和 
	while(t--)
	{
		cin>>n>>m;
		cout<<d[n][min(n,m)]<<'\n';
		//注意，上方只做出了三角形形状的前缀和图形，但是题目中并没有保证m<n
		//因此，第二维应该是min(n,m)，比如在6个数里选10个，答案数等同于6个里选6个 
	}
	return 0;	
}

前缀和

#include<bits/stdc++.h>
using namespace std;
int T,k,n,m;
int c[2005][2005];
int sum[2005][2005];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>T>>k;
//组合数求解
	for(int i=0;i<=2001;i++)
		for(int j=0;j<=i;j++)
			if(i==0||i==j)
				c[i][j]=1;
			else
				c[i][j]=(c[i-1][j-1]+c[i-1][j])%k;
//二维前缀和求解
	for(int i=1;i<=2001;i++)
		for(int j=1;j<=2001;j++)
			if(c[i][j]==0&&j<=i)//注意算组合数时满足j<=i
				sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+1;
			else
				sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];
	while(T--)
	{
		cin>>n>>m;
		cout<<sum[n][m]<<"\n";
	}
	return 0;
}