odd doctor 已更新

Good Sequence

Time Limit
1s
Memory Limit
262144KB
Judge Program
Standard
Ratio(Solve/Submit)
66.67%(2/3)
Description:

众所周知,
现有一个长度为 2*n 的序列,包含 n 个 1 和 n 个 -1 .
对于一个这样的序列,如果该序列的任意前缀和不小于 0 ,则称此序列为 "Good Sequence" ,
现给出 n ,求出长度为 2*n 的序列中有多少个 "Good Sequence" 。

Input:

输入包含多组数据。第一行为一个正整数 T ( 1 T 100 ),表示有 T 组测试数据。
对于每组测试数据,仅有一行包含一个整数 n ( 1 n 1000 )表示序列中分别含有 n 个 1 和 -1 .

Output:

对于每组测试数据,
输出一行包含一个整数,表示长度为 2*n 的序列中含有 "Good Sequence" 的个数,答案可能会很大,请将结果对 (313091025) 取模。


Sample Input:
3
3
1
999
Sample Output:
5
1
81644615
Hint:

当n=3时,有5个"Good Sequence"分别为:(1,1,1,-1,-1,-1),(1,1,-1,1,-1,-1),(1,1,-1,-1,1,-1),(1,-1,1,1,-1,-1),(1,-1,1,-1,1,-1).当n=1时,有1个"Good Sequence",为(1,-1).

Source:

neromy


Submit