Good Sequence
Time Limit
1s
Memory Limit
262144KB
Judge Program
Standard
Ratio(Solve/Submit)
100.00%(1/1)
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).
Submit