【u104】组合数
2024-10-08 03:34:39
Time Limit: 1 second
Memory Limit: 128 MB
【问题描述】
组合数C(N, K)表示了N个数字不重复地选取K个作组合的方案数。
C(N, K) = N!/(N-M)!M!
当然,在取余数的条件下,由于除法的限制,上述公式求C(N, K) mod H不方便,并且高精度除法也不容易写,所以一般情况下我们采取的是下列方法。
若N,K不大,可以通过递推的方法求出所有组合数。
首先,N个数取0个数显然只有1种方案,那就是什么都不取;
接着,N个数取N个数的组合显然也只有1种方案。
所以C(N, 0) = 1,C(N, N) = 1
其他情况下有递推式C(N, K) = C(N - 1, K) + C(N – 1, K – 1),这样就可以通过递推求出所有组合数。
你可以看到,其实结果其实就是杨辉三角形。
现在对于给定的N和K,请输出C(N, K) mod 100003。
【输入格式】
输入文件com.in的第1行为两个非负整数N,K。
【输出格式】
输出文件com.out包括1个非负整数,
【数据规模】
对于100%的数据,N≤1000,K≤1000。
Sample Input1
4 2
Sample Output1
6
【题解】
高中学二项式定理的时候有接触到一点。所以还是会有点印象的。那些c(n,k)什么的,实际上是和杨辉三角对应的。
然后用给的递推式递推就可以了。注意取模;
【代码】
#include <cstdio> int n,k,c[1001][1001]; int main()
{
scanf("%d%d",&n,&k);
for (int i = 0;i<= n;i++)
c[i][0] = 1,c[i][i] = 1; //这是边界条件。杨辉三角可以不用但是c(n,0)输出应该是1而不是0
for (int i = 1;i <= n;i++)
for (int j =0;j <= i;j++) //一边取模一边递推。
c[i][j] = (c[i-1][j]+c[i-1][j-1]) % 100003;
printf("%d",c[n][k]);
return 0;
}
最新文章
- selenium 3.0 beta2 初体验
- `cocos2dx非完整` 日志模块 增量更新
- Mac添加环境变量的三种方法
- 网络笔记01-2 scoket
- 【Python】实践笔记
- MATLAB conv2卷积的实现
- ios5和ios6横竖屏支持及ipad和iphone设备的判断
- Tempdb怎么会成为性能瓶颈
- 自动化测试 -- 通过Cookie跳过登录验证码
- __builtin_popcount(n)
- Mego(05) - Mego Tools使用教程
- Django框架的使用教程--类视图-中间间-模板[六]
- python3网络爬虫(4):python3安装Scrapy
- DBNull与Null的区别
- 【题解】 Luogu P4312 / SP4155 [COCI 2009] OTOCI / 极地旅行社
- sqlalchemy精华版
- sql server 大批数据插入时,时间过长的问题
- 使用jsonp进行跨站点数据访问
- C++ STL 学习笔记__(5)list
- Scrapy爬虫框架之爬取校花网图片
热门文章
- 关于sublime text2的一些问题(为解决)
- 转:国内从事CV相关的企业
- javascript正则表达式和字符串RegExp
- 2019-9-2-dotnet-命名管道名字长度限制
- MacOS配置双网
- navicat for mysql 在Mac上安装后没有连接列表,就是左边的那一列连接项目怎么办?
- 2018-8-10-win10-uwp-如何创建修改保存位图
- Gym - 101480K_K - Kernel Knights (DFS)
- Java练习 SDUT-1211_英文金曲大赛
- LeetCode58 Length of Last Word