题目描述

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

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

其中 n!=1×2××nn!=1\times2\times\cdots\times n;特别地,定义 0!=1。

小葱想知道如果给定 n,m 和 k,对于所有的 0in,0jmin(i,m)0\leq i\leq n,0\leq j\leq \min \left ( i, m \right )有多少对 (i,j) 满足 k(ij)k|\binom{i}{j}

输入格式

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

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

输出格式

共 t 行,每行一个整数代表所有的 0in,0jmin(i,m)0\leq i\leq n,0\leq j\leq \min \left ( i, m \right ) 中有多少对 (i,j) 满足 k(ij)k|\binom{i}{j}

输入输出样例

输入 #1

1 2
3 3

输出 #1

1

输入 #2

2 5
4 5
6 7

输出 #2

0
7

说明/提示

【样例1说明】

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

【子任务】

img

  • 对于全部的测试点,保证 0n,m2×1031t1040 \leq n, m \leq 2 \times 10^3,1 \leq t \leq 10^4

题目分析

利用组合的一个性质:

Cnm=Cn1m+Cn1m1C_{n}^{m}=C_{n-1}^{m}+C_{n-1}^{m-1}

可以预处理Cij,0jinC_i^j,0\leq j \leq i\leq n 。复杂度O(n2)O(n^2)

c[0][0]=c[1][0]=c[1][1]=1;
for(int i=2;i<=N-5;i++){
    for(int j=0;j<=i;j++){
        c[i][j]=c[i-1][j]+c[i-1][j-1];
    }
}

但是本题n的范围达到了2×1032\times 10^3 。会超出long long数据范围。并且,每次得到范围n和m之后,需要遍历C00CnmC_0^0\sim C_n^m 统计能整除k的元素个数。重复t次,整体复杂度为O(tnm)O(t· n· m) ,会超时。

image-20220414160820385

此时需要解决两个问题:

  1. 范围过大导致答案错误
  2. 重复遍历,时间超时

C00CnnC_0^0\sim C_n^n 的所有值都是固定的,每次遍历C00CnmC_0^0\sim C_n^m 统计的话,很多都是重复统计了。此时可以利用前缀和提前统计区间内的满足的总和。

再来看数太大的问题,根据组合数的性质:Cnm=Cn1m+Cn1m1C_{n}^{m}=C_{n-1}^{m}+C_{n-1}^{m-1} ,且我们只需要统计能否整除k的个数,那么利用同余性质,C[i][j]中存放Cnm%kC_n^m\% k 的结果即可。

代码实现

#include <iostream>
#include <cstdio>
using namespace std;
const int N=2e3+5;
typedef long long ll;
ll c[N][N];//c[i][j]为C(i,j)%k
ll s[N][N];//s[i][j]为c(i,0)~c(i,j)的能整除k的元素总数
ll num[N];//num[i]为 C(0~i,?) 能整除k的元素总数
int main(){
	int t,k;
	int n,m;
	cin>>t>>k;
	//预处理 c[i][j] 为C[i][j]%k
	//C(i,j)=C(i-1,j)+C(i-1,j-1)
	c[0][0]=c[1][0]=c[1][1]=1%k;
	num[0]=!c[0][0];
	num[1]=!c[1][0]+!c[1][1];
	for(int i=0;i<=N-5;i++){
		for(int j=0;j<=i;j++){
			c[i][j]=(c[i-1][j]%k+c[i-1][j-1]%k)%k;
			num[i]+=(!c[i][j]);//累加C(i,j) 的能整除k的总和
			s[i][j]=s[i][j-1]+!c[i][j];//前缀和 计算 s[i][j]
		}
		num[i]+=num[i-1];//前缀和统计总和
	}
	
	while(t--){
		cin>>n>>m;
		ll cnt=0;//满足条件的总数
		if(m>=n) cnt=num[n];//C(0,0)~C(n,m)都要算上,直接累加计算好的总和
		else{//m<n
			cnt=num[m];// 先累加C(0,0)~C(m,m)的满足条件的总和
			for(int i=m+1;i<=n;i++){//遍历C(m+1,?)~C(n,?) 
				cnt+=(s[i][m]);//累加每层 C(i,0)~C(i,m) 满足条件的元素总数
			}
		}
		cout<<cnt<<endl;
	}
	return 0;
}

image-20220414161817887

Q.E.D.


( ノ^ω^)ノ゚ 稻 花 香 里 说 丰 年 , 听 取 WA 声 一 片 。(╥╯^╰╥)