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

题目背景

NOIP2016 提高组 D2T1

题目描述

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

$$\left(\genfrac{}{}{0ex}{}{n}{m}\right)=\frac{n!}{m!(n-m)!}$$

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

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

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

1 2
3 3

输出 #1

1

输入输出样例 #2

输入 #2

2 5
4 5
6 7

输出 #2

0
7

说明/提示

【样例1说明】

在所有可能的情况中，只有 $\left(\genfrac{}{}{0ex}{}{2}{1}\right)=2$ 一种情况是 $2$ 的倍数。

【子任务】

• 对于全部的测试点，保证 $0\le n,m\le 2\times 10^3$，$1\le t\le 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;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容