打卡信奥刷题（1269）用C++实现信奥 P2822 [NOIP 2016 提高组] 组合数问题

rogeliu

5408人浏览 · 2025-05-06 13:57:44

rogeliu · 2025-05-06 13:57:44 发布

P2822 [NOIP 2016 提高组] 组合数问题

题目背景

NOIP2016 提高组 D2T1

题目描述

组合数 $(nm)\binom{n}{m}$ 表示的是从 $n$ 个物品中选出 $m$ 个物品的方案数。举个例子，从 $(1, 2, 3)$ 三个物品中选择两个物品可以有 $(1, 2), (1, 3), (2, 3)$ 这三种选择方法。根据组合数的定义，我们可以给出计算组合数 $(nm)\binom{n}{m}$ 的一般公式：

$(nm)=n!m!(n−m)!\binom{n}{m}=\frac{n!}{m!(n-m)!}$

其中 $n!=1×2×⋯×nn!=1\times2\times\cdots\times n$ ；特别地，定义 $0! = 1$ 。

小葱想知道如果给定 $n, m$ 和 $k$ ，对于所有的 $0≤i≤n,0≤j≤min⁡(i,m)0\leq i\leq n,0\leq j\leq \min \left ( i, m \right )$ 有多少对 $(i, j)$ 满足 $k∣(ij)k\mid\binom{i}{j}$ 。

输入格式

第一行有两个整数 $t, k$ ，其中 $t$ 代表该测试点总共有多少组测试数据， $k$ 的意义见问题描述。

接下来 $t$ 行每行两个整数 $n, m$ ，其中 $n, m$ 的意义见问题描述。

输出格式

共 $t$ 行，每行一个整数代表所有的 $0≤i≤n,0≤j≤min⁡(i,m)0\leq i\leq n,0\leq j\leq \min \left ( i, m \right )$ 中有多少对 $(i, j)$ 满足 $k∣(ij)k\mid\binom{i}{j}$ 。

输入输出样例 #1

输入 #1

1 2
3 3

输出 #1

输入输出样例 #2

输入 #2

2 5
4 5
6 7

输出 #2

0
7

说明/提示

【样例1说明】

在所有可能的情况中，只有 $(21)=2\binom{2}{1} = 2$ 一种情况是 $2$ 的倍数。

【子任务】

对于全部的测试点，保证 $\leq n, m \leq 2 \times 10^3$ ， $\leq t \leq 10^4$ 。

C++实现

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll t,flag[2002][2002];
int k,f[2002][2002];
void yh(){
	f[0][0]=f[1][0]=f[1][1]=1;
	for (int i=2;i<=2000;i++){
		f[i][0]=1;
		for (int j=1;j<=i;j++){
			f[i][j]=(f[i-1][j-1]%k+f[i-1][j]%k)%k;
			flag[i][j]=flag[i-1][j]+flag[i][j-1]-flag[i-1][j-1];
			if (f[i][j]==0) flag[i][j]++;
		}
		flag[i][i+1]=flag[i][i];
	}
}
int main (){
	scanf("%lld%d",&t,&k);
	yh();
	while (t--){
		int m,n;
		scanf("%d%d",&n,&m);
		if(m>n) printf("%lld\n",flag[n][n]);
		else printf("%lld\n",flag[n][m]);
	}
	return 0;
}