题目大意:有n匹马比赛,问说有多少种排名情况,可以并列。
解题思路:dp[i][j]表示i匹马,最后一名为j的情况,转移方程dp[i][j]=(dp[i−1][j]+dp[i−1][j−1])∗j
#include <cstdio>
#include <cstring>
typedef long long ll;
const int N = 1005;
const ll MOD = 10056;
ll dp[N][N], f[N];
void init () {
memset(f, 0, sizeof(f));
memset(dp, 0, sizeof(dp));
dp[1][1] = 1;
for (ll i = 1; i <= 1000; i++) {
for (ll j = 1; j <= i; j++) {
dp[i+1][j] = (dp[i+1][j] + dp[i][j] * j) % MOD;
dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j] * (j + 1)) % MOD;
f[i] = (f[i] + dp[i][j]) % MOD;
}
}
}
int main () {
init();
int cas, n;
scanf("%d", &cas);
for (int i = 1; i <= cas; i++) {
scanf("%d", &n);
printf("Case %d: %lld\n", i, f[n]);
}
return 0;
}
分享到:
相关推荐
判断输入字符串是否为镜像或回文串。 来源于UVaOJ - 401. 水题。
开源项目-codingsince1985-UVa#uva-online-judge-solutions-in-golang.zip,两年来每天都在解决一个uva在线裁判问题,算起来…
uva705 Slash Maze 的代码,在UVaOJ上通过
PDF试题
uva532 Dungeon Master的源代码,并且AC了
Algorithm-UVA-Solutions-in-Python.zip,python 3中各种uva(acm)问题的解决方案。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
这是UVA133 TheDoleQueue救济金发放问题,经典的算法问题。初学算法的人要对这种算法非常熟悉并且能熟练运用。
tpcw-nyu-uva-client 客户端
leetcode 2 算法-Java UVa Online Judge(ACM-ICPC Live ...使用:数组、哈希表、链表、二分搜索、动态规划、堆栈、堆、reedy、排序、树 DFS、BFS、图、二分搜索树、递归、记忆、队列、映射等。...Uva-ACM-ICPC