HDU 4828 Grids

  • 2018-08-07
  • 11
  • 0

题目:

度度熊最近很喜欢玩游戏。这一天他在纸上画了一个2行N列的长方形格子。他想把1到2N这些数依次放进去,但是为了使格子看起来优美,他想找到使每行每列都递增的方案。不过画了很久,他发现方案数实在是太多了。度度熊想知道,有多少种放数字的方法能满足上面的条件?

Input:

第一行为数据组数T(1<=T<=100000)。
然后T行,每行为一个数N(1<=N<=1000000)表示长方形的大小。

Output:

对于每组数据,输出符合题意的方案数。由于数字可能非常大,你只需要把最后的结果对1000000007取模即可。

Sample Input:

2
1
3

Sample Output:

Case #1:
1
Case #2:
5

Hint:

对于第二组样例,共5种方案,具体方案为:

题目链接

卡特兰数列。

Catalan(n)=\frac{Catalan(n-1)\times (4\times n-2)}{n+1} \tag{卡特兰数列递推式}

因为本题数据有点大且需要取模,所以在递推中需要使用逆元

(n+1)\times x\equiv 1(mod (1e9+7))

\therefore Catalan(n)=Catalan(n-1)\times (4\times n-2)\times x

加上取模即可。

AC代码:

评论

还没有任何评论,你来说两句吧