5177：Box

题目描述

Gorwin is a Goodness while Vivin is a Dios. Vivin has hidden to love Gorwin for long time. Vivin believes that Dios will one day get a counter attack. Today is Valentines' Day, Vivin gets up the encourage to make an engagement with Gorwin. During the dating, they play a game. There are $2n$ cube boxes of the same size on the ground, Gorwin and Vinvin will take $n$ boxes respectively and then pile a tower of $n$ boxes. They will take $2n$ seconds to pile the towers. In each second, only one people can take exact a box and pile it to his/her own tower. However, according to the doctrine of “lady first”, the height of Vinvin’s tower should not be higher than Gorwin’s during every second in the game.

You are expected to write a program to calculate how many different operation sequences to complete the game. For the answer may be very large, please output the answer modular $3814697265625$ instead.

输入解释

There are multiple test cases. In the first line of the input file there is an integer $T$ indicates the number test cases.
In the next $T$ lines, each line contains an integer $n$ which is mentioned above.

[Technical Specification]
All input items are integers.
$0< T <= 20, 1<=n<=1000000000000000000({10}^{18})$

输出解释

For each case，the output should occupies exactly one line. The output format is Case #id: ans, here id is the data number starting from 1; ans is the result of answer modular $3814697265625$.

输入样例

2
1
2

输出样例

Case #1: 1
Case #2: 2

提示

For the first case, the is only one way to accomplish the game, i.e. step 1, Gorwin piles one box to her tower; step 2 Vinvin piles the last box to his tower. Because Vinvin’s tower should not be higher than Gorwin’s in every second during the game, so step 1 Vinvin can’t take a box to pile to his tower.

For the second case, 
Way 1: step1 Gorwin piles one box; step2 Gorwin piles one box; step3 Vinvin piles one box; step4 Vinvin piles one box;
Way 2: step1 Gorwin piles one box; step2 Vinvin piles one box; step3 Gorwin piles one box; step4 Vinvin piles one box.
There is no other valid way to realize the game. So the answer to the second case is 2.

来自杭电HDUOJ的附加信息

Recommend

hujie

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 Valentine's Day Round

源链接： HDU-5177

最后修改于 2020-10-25T23:20:27+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
16000/8000MS(Java/Others)	65536/65536K(Java/Others)