洛谷 P2822 组合数问题
2024-10-21 03:53:28
题目描述
组合数C_n^mCnm表示的是从n个物品中选出m个物品的方案数。举个例子,从(1,2,3) 三个物品中选择两个物品可以有(1,2),(1,3),(2,3)这三种选择方法。根据组合数的定 义,我们可以给出计算组合数的一般公式:
C_n^m=\frac{n!}{m!(n - m)!}Cnm=m!(n−m)!n!
其中n! = 1 × 2 × · · · × n
小葱想知道如果给定n,m和k,对于所有的0 <= i <= n,0 <= j <= min(i,m)有多少对 (i,j)满足C_i^jCij是k的倍数。
输入输出格式
输入格式:
第一行有两个整数t,k,其中t代表该测试点总共有多少组测试数据,k的意义见 【问题描述】。
接下来t行每行两个整数n,m,其中n,m的意义见【问题描述】。
输出格式:
t行,每行一个整数代表答案。
输入输出样例
输入样例#1:
1 2
3 3
输出样例#1:
1
输入样例#2:
2 5
4 5
6 7
输出样例#2:
0
7
说明
【样例1说明】
在所有可能的情况中,只有C_2^1 = 2C21=2是2的倍数。
【子任务】
题解:杨辉三角求组合数+前缀和
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std; int c[][],sum[][];
int t,k,n,m; int main(){
scanf("%d%d",&t,&k);
for(int i=;i<=;i++){
for(int j=;j<=i;j++){
if(j==)c[i][j]=;
else if(i==j)c[i][j]=;
else c[i][j]=(c[i-][j]%k+c[i-][j-]%k)%k;
}
}
sum[][]=c[][]==?:;
for(int i=;i<=;i++){
for(int j=;j<=;j++){
sum[i][j]=sum[i-][j]+sum[i][j-]-sum[i-][j-];
if(c[i][j]==&&i>=j)sum[i][j]++;
}
}
while(t--){
scanf("%d%d",&n,&m);
printf("%d\n",sum[n][m]);
}
return ;
}
最新文章
- [vivado系列]Zynq开发常用文档
- git 常用技巧
- Form_通过Zoom客制化跳转页面功能(案例)
- 论职务犯罪案件侦查 z
- win7系统服务print spooler 无法启动解决方法(开启及关闭方法)
- Python练习题 027:对10个数字进行排序
- 路径中“/” ";\"; ";\\";的区别
- 基于visual Studio2013解决面试题之1002公共子串
- ThinkPHP使用方法
- python 线程/线程锁/信号量
- Delphi7连接MySql数据库-DBGrid控件显示数据
- 利用Flume将MySQL表数据准实时抽取到HDFS
- day 43 数据库的密码的的更改如何操作
- VB6 CHECK is run as admin privilege
- Idea热部署jrebel失败
- string.format的用途联想
- (转)Spring Boot中使用AOP统一处理Web请求日志
- Markdown语法初体验
- Linux内核分析第三周学习博客——跟踪分析Linux内核的启动过程
- 如何选择正确的angular2学习曲线?
热门文章
- 026_默认的MapReduce Driver(最小驱动问题)
- 【leetcode刷题笔记】Word Ladder II
- jQuery带闹钟的数字时钟
- ORA-01034和ORA-27101的错误
- php数组函数-array_merge()
- redis 数据导入导出,实例内db迁移
- 吴恩达深度学习笔记(十二)—— Batch Normalization
- POJ 3253 Fence Repair 贪心+优先队列
- Fatal error: cannot create &#39;R_TempDir&#39;
- 【P1582】倒水(数论??暴力!!)