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.

Both first
horse₁ first and horse₂ second
horse₂ first and horse₁ 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

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

Sample Output

Case 1: 1
Case 2: 3
Case 3: 13

Source

Root :: AOAPC II: Beginning Algorithm Contests (Second Edition) (Rujia Liu) :: Chapter 10. Maths :: Examples
Root :: Prominent Problemsetters :: Md. Mahbubul Hasan

Root :: AOAPC I: Beginning Algorithm Contests -- Training Guide (Rujia Liu) :: Chapter 2. Mathematics :: Counting :: Exercises: Intermediate

Submit Status

/* ***********************************************
Author        :CKboss
Created Time  :2015年01月07日 星期三 21时21分14秒
File Name     :UVA12034.cpp
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;

const int mod = 10056;
int n;

int C[2000][2000];
int f[2000];

void init()
{
	for(int i=0;i<1100;i++) C[i][0]=C[i][i]=1;
	for(int i=2;i<1100;i++)
		for(int j=1;j<i;j++)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
	f[0]=1; f[1]=1; f[2]=3; f[3]=13;
	for(int i=4;i<=1000;i++)
	{
		int ans=0;
		for(int j=1;j<=i;j++)
		{
			ans=(ans+C[i][j]*f[i-j])%mod;
		}
		f[i]=ans;
	}
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
	
	init();
	int T_T,cas=1;
	scanf("%d",&T_T);
	while(T_T--)
	{
		scanf("%d",&n);
		printf("Case %d: %d\n",cas++,f[n]);
	}
    
    return 0;
}

UVA 12034 Race

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们