【题解】组合数问题
问题 组合 题解
2023-06-13 09:11:41 时间
题目描述
输入格式
第一行有两个整数 t,k,其中 t 代表该测试点总共有多少组测试数据,k 的意义见问题描述。
接下来 t 行每行两个整数 n,m,其中 n,m 的意义见问题描述。
输出格式
共 t 行,每行一个整数代表所有的 0\leq i\leq n,0\leq j\leq \min \left ( i, m \right )中有多少对 (i,j) 满足 k|\binom{i}{j}。
输入输出样例
输入 #1
1 2
3 3
输出 #1
1
输入 #2
2 5
4 5
6 7
输出 #2
0
7
说明/提示
【样例1说明】
在所有可能的情况中,只有 2\binom{2}{1} 一种情况是 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\times 10^3 。会超出long long
数据范围。并且,每次得到范围n和m之后,需要遍历C_0^0\sim C_n^m 统计能整除k的元素个数。重复t次,整体复杂度为O(t· n· m),会超时。
此时需要解决两个问题:
- 范围过大导致答案错误
- 重复遍历,时间超时
代码实现
#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;
}
Q.E.D.
相关文章
- Wiztalk主题学术报告:ChatGPT的技术发展与问题浅析——哈尔滨工业大学车万翔教授
- 【组合数学】错排问题 ( 递推公式 | 通项公式 | 推导过程 ) ★
- MySQL添加索引特点及优化问题
- 解决Linux远程登录遇到的问题(linux无法远程登录)
- Linux重装网卡驱动:解决网络问题的绝佳方式(linux重装网卡驱动)
- 嵌入式Linux系统的问题及解决方案(嵌入式linux系统缺点)
- 时间解决Java程序中Redis过期时间设置问题(redisjava过期)
- Linux 数据库解决乱码问题(linux数据库乱码)
- 使用Redis监控工具轻松解决日常管理问题(常用redis 监控工具)
- MySQL导入视图失败原来可能是这个问题(mysql不能导入视图)
- 求助Oracle中解决不确定文件名的问题(oracle不确定文件名)