专栏文章

P2822 [NOIP2016 提高组] 组合数问题 题解

ZZskioaert1106
P2822题解参与者 9已保存评论 11

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
11 条
当前快照
1 份
快照标识符
@miqnrpi6
此快照首次捕获于
2025/12/04 07:48
3 个月前
此快照最后确认于
2025/12/04 07:48
3 个月前
查看原文
题目传送门：P2822 [NOIP2016 提高组] 组合数问题
原文，但是被拒了。
众所周知杨辉三角表现在二维数组里就是 fi,j=fi−1,j−1+fi−1,jf_{i,j}=f_{i-1,j-1}+f_{i-1,j}。
而众所又周知：
(n−1m−1)+(n−1m)=(n−1)!(m−1)![(n−1)−(m−1)]!+(n−1)!m![(n−1)−m]!=(n−1)!mm!(n−m)!+(n−1)!(n−m)m!(n−m)!=(n−1)!(m+n−m)m!(n−m)!=n!m!(n−m)!=(nm)\begin{equation} \begin{aligned} &\binom{n-1}{m-1}+\binom{n-1}{m}\\ \\=&\frac{(n-1)!}{(m-1)![(n-1)-(m-1)]!}+\frac{(n-1)!}{m![(n-1)-m]!}\\ \\ =&\frac{(n-1)!m}{m!(n-m)!}+\frac{(n-1)!(n-m)}{m!(n-m)!}\\ \\ =&\frac{(n-1)!(m+n-m)}{m!(n-m)!}\\ \\ =&\frac{n!}{m!(n-m)!}\\ \\ =&\binom{n}{m} \end{aligned} \end{equation}
所以组合数可以直接用杨辉三角来推。2×1032\times 10^3 的数据范围正好开二维数组，而之前会爆 long long 却无计可施的原因是除法不能取模，现在变成加法就可以了。而我只关心它模 kk 的余数。于是：
CPP
const int MAXN=2000;
int t,n,m;
long long k;
int C[2003][2003];//存 C(n,m) 模 k 后的余数
int main(){
	cin>>t>>k;
	for(int i=0;i<=MAXN;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]+C[i-1][j])%k;
    	}
    }
	while(t--){
		int ans=0;
		cin>>n>>m;
		for(int i=0;i<=n;i++){
			int mn=min(i,m);
			for(int j=0;j<=mn;j++){
				ans+=(C[i][j]%k==0);
			}
		}
		cout<<ans<<'\n';
	}
	return 0;
}
得分：9090pts。
剩下的两个点 TLE 了。
我发现，每次求的东西都是从 00 遍历到 nn，然后每维再从 00 遍历，这样求一个二维相邻部分的状态和。所以可以很容易地使用二维前缀和优化。
CPP
#include<iostream>
using namespace std;
const int N=2000;
int t,n,m,k;
int C[2003][2003];//杨辉三角
int d[2003][2003];//前缀和
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);  
	cin>>t>>k;
	for(int i=0;i<=N;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]+C[i-1][j])%k;
		}
	}
	for(int i=0;i<=N;i++){
		for(int j=0;j<=N;j++){
			if(j<=i)d[i][j]=d[i-1][j]-d[i-1][j-1]+d[i][j-1]+(C[i][j]%k==0);//二维前缀和的式子
			else d[i][j]=d[i][i];//杨辉三角的空白部分要填充上
		}
	}
	while(t--){
		cin>>n>>m;
		cout<<d[n][min(n,m)]<<'\n';//答案
	}
	return 0;
}
得分：100100pts。

评论

共 11 条评论，欢迎与作者交流。

正在加载评论...