UVa 12034 Race (组合数学)

题目

题目大意

(A)、(B)两人赛马, 最终名次有(3)种可能: 并列第一; (A)第一(B)第二; (B)第一(A)第二。输入(n)((1 ≤ n ≤1000)), 求(n)人赛马时最终名次的可能性的个数除以(10056)的余数。

题解

设答案为(f(n))。假设第一名有(i)个人， 有(n choose i)种可能性, 接下来有(f(n - i))种可能性, 因此答案为(sum {n choose i}f(n - i))。

代码

#include <cstdio>
const int kMod(10056);
int C[1010][1010], dp[1010], T, n;
int main(int argc, char const *argv[]) {
  for (register int i(0); i <= 1000; ++i) {
    C[i][0] = 1;
  }
  for (register int i(1); i <= 1000; ++i) {
    for (register int j(1); j <= 1000; ++j) {
      C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % kMod;
    }
  }
  dp[0] = 1;
  for (register int i(1); i <= 1000; ++i) {
    for (register int j(1); j <= i; ++j) {
      dp[i] = (dp[i] + C[i][j] * dp[i - j]) % kMod;
    }
  }
  scanf("%d", &T);
  for (register int cases(1); cases <= T; ++cases) {
    scanf("%d", &n);
    printf("Case %d: %d
", cases, dp[n]);
  }
  return 0;
}