uva 12034 Race

2024-03-24 08:48

文章标签 uva race 12034

本文主要是介绍uva 12034 Race，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题：
Disky and Sooma, two of the biggest mega minds of Bangladesh went to a far country. They ate, coded and wandered around, even in their holidays. They passed several months in this way. But everything has an end. A holy person, Munsiji came into their life. Munsiji took them to derby (horse racing).Munsiji enjoyed the race, but as usual Disky and Sooma did their as usual task instead of passing some romantic moments. They were thinking- in how many ways a race can finish! Who knows, maybe this is their romance!In a race there are n horses. You have to output the number of ways the race can finish. Note that,more than one horse may get the same position. For example, 2 horses can finish in 3 ways.
1. Both first
2. horse 1 first and horse 2 second
3. horse 2 first and horse 1 second
Input
Input starts with an integer T (≤ 1000), denoting the number of test cases. Each case starts with a
line containing an integer n (1 ≤ n ≤ 1000).
Output
For each case, print the case number and the number of ways the race can finish. The result can be
very large, print the result modulo 10056.
Sample Input
3
1
2
3
Sample Output
Case 1: 1
Case 2: 3
Case 3: 13
大意：
A、B两人赛马,最终名次有3种可能:并列第一;A第一B第二;B第一A第二。输
入n(1≤n≤1000),求n人赛马时最终名次的可能性的个数除以10056的余数。

#include <bits/stdc++.h>
using namespace std;
//fstream in,out;
const int mod=10056;
int f[1001];
int c[1001][1001];
void C()
{int i,j;memset(c,0,sizeof(c));for(i=0;i<=1000;i++)c[0][i]=c[1][i]=1;for(i=0;i<=1000;i++)c[i][i]=1;for(i=0;i<=1000;i++)c[i][0]=1;for(i=1;i<=1000;i++){for(j=1;j<=1000;j++){if(i!=j)c[i][j]=(c[i-1][j]%mod+c[i-1][j-1]%mod)%mod;}}
}
int main()
{ios::sync_with_stdio(false);int n,m;C();f[0]=f[1]=1;for(int i=2;i<=1000;i++){int tmp=0;for(int j=1;j<=i;j++)tmp+=f[i-j]*c[i][j]%mod;f[i]=tmp%mod;}cin>>m;for(int i=1;i<=m;i++){cin>>n;cout<<"Case "<<i<<": "<<f[n]<<endl;}return 0;
}