【4.3火题】move

Description

设P(n)为从(0,0)移动到点(n,0)的不同路径数目,移动的方式有以下三种:(x,y)->(x+1,y-1),(x,y)->(x+1,y),(x+y)->(x+1,y+1),并且路径不能和第四象限有交集。求P(n),并对109+7取模。

Input

第一行一个整数T,表示数据组数。

对于每组数据,一行一个整数n。

Output

对于每组数据,输出答案。

Data Range

20%:n≤10;
50%:n≤10000;
100%:n≤106,T≤10。

Solution

终于有一道会做的了。。然而没预处理逆元被卡常了。。很生气。。

如果不能横着走的话显然答案为Catalan数

那么枚举一下横着走多少步,乘起来就可以了。。

update:我特么居然不知道可以O(n)预处理阶乘逆元。。我个智障

首先把最后一个阶乘的逆元处理出来然后每次乘上上一个数就行了。。

$$\prod_{i=1}^k i^{-1}=(\prod_{i=1}^{k+1} i^{-1})\times(k+1)$$

于是预处理复杂度O(n)。。计算复杂度O(Tn)。。

说点什么

  Subscribe  
提醒