题解 008 题目 P2822

题目分析

数据范围中提到 $0\le n,m \le 2\times 10^3$ ，因此可以想到可以使用组合数递推式 $\tbinom{n}{m}=\tbinom{n-1}{m-1}+\tbinom{n-1}{m}$ 进行预处理，时间复杂度 $O(nm)$ 。
对于每次询问，如果暴力查找的话时间复杂度为 $O(nm)$ ，只能拿到部分分数。由于每次询问的 $k$ 都一样，还是访问子矩阵，可以考虑二维前缀和。如果 $k\mid\tbinom{n}{m}$ ，设矩阵 $x$ 的 $x_{n,m}$ 为 $1$ ，否则为 $0$ ，每次询问输出 $x$ 前缀和即可。时间复杂度 $O(1)$ 。

通过代码

CPP

#include<iostream>
using namespace std;
int t,k,n,m,c[2005][2005],x[2005][2005],a[2005][2005];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>t>>k;
	for (int i=0;i<=2000;i++){
		for (int j=0;j<=i;j++){
			if (j==0||j==i) c[i][j]=1;
			else c[i][j]=(c[i-1][j-1]%k+c[i-1][j]%k)%k; // 记得取模。
			if (c[i][j]==0) x[i][j]+=1; // 如果 c[i][j] 整除 k，将 x[i][j] 记为 1，查询时输出它的前缀和。
		}
	} // 预处理，注意边界情况。
	for (int i=0;i<=2000;i++){
		for (int j=0;j<=2000;j++){
			if (i>0&&j>0) a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+x[i][j];
			else if (i>0&&j==0) a[i][j]=a[i-1][j]+x[i][j];
			else if (i==0&&j>0) a[i][j]=a[i][j-1]+x[i][j];
			else a[i][j]=x[i][j];
		}
	} // 计算 x 数组的前缀和，同样记得注意边界情况。
	while (t--){
		cin>>n>>m;
		cout<<a[n][m]<<"\n";
	} // 每次访问，输出前缀和。
	return 0;
}

题解 008 题目 P2822

文章操作

题目分析

通过代码

相关推荐

评论

题解 008 题目 P2822