UVa 12034 - Race(递推 + 杨辉三角)
2024-08-27 13:28:23
链接:
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3185
题意:
A、B两人赛马,最终名次有3种可能:并列第一;A第一B第二;B第一A第二。
输入n(1≤n≤1000),求n人赛马时最终名次的可能性的个数除以10056的余数。
分析:
设答案为f(n)。假设第一名有i个人,有C(n,i)种可能性,接下来有f(n-i)种可能性,因此答案为∑C(n,i)f(n-i)。
组合数的计算可以用杨辉三角递推。
代码:
import java.io.*;
import java.util.*; public class Main {
static final int MOD = 10056;
static final int UP = 1000 + 5;
static int f[] = new int[UP], C[][] = new int[UP][UP]; static void constant() {
for(int n = 0; n < UP; n++) {
C[n][0] = C[n][n] = 1;
for(int m = 1; m < n; m++)
C[n][m] = (C[n-1][m-1] + C[n-1][m]) % MOD;
} f[0] = 1;
for(int n = 1; n < UP; n++)
for(int i = 1; i <= n; i++)
f[n] = (f[n] + C[n][i] * f[n-i]) % MOD;
} public static void main(String args[]) {
Scanner cin = new Scanner(new BufferedInputStream(System.in));
constant(); int T = cin.nextInt();
for(int cases = 1; cases <= T; cases++) {
int n = cin.nextInt();
System.out.printf("Case %d: %d\n", cases, f[n]);
}
cin.close();
}
}
最新文章
- jq pagination分页 全选、单选的思考
- 浅谈Oracle中物理结构(数据文件等。。。)与逻辑结构(表空间等。。。。。)
- SSH实例(2)
- 《ASP.NET1200例》在DataList里编辑和删除数据
- UITableView多选全选
- js解决click事件点击事件间隔方法
- leetcode find median sorted arrays python
- 开源Math.NET基础数学类库使用(17)C#计算矩阵条件数
- 给ubuntu的swap分区增加容量
- vue新手入门——谈谈理解
- C语言--测试电脑存储模式(大端存储OR小端存储)
- 非常好用的sersync同步工具
- echarts-map-区县
- Javascript面向对象编程(二)
- js中用户名的正则(字符,数字,下划线,减号)
- 部署eclipse项目到tomcat
- PHP实现字符串转义和还原
- 返回JSON格式(二十五)
- 2017/05/20 java 基础 随笔
- Dynamics CRM 2011 怎么根据记录的etc参数值找到实体英文名和根据etc参数值或英文名称找到其实体中文名称