2004 . 棋盤遊戲 (Board)

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Adrien Wu
AC×29New TIOJ ?

User's AC Ratio

98.4% (62/63)

Submission's AC Ratio

63.6% (150/236)

Tags

CKsim 2017-CKsim-北市模擬

Description

現在有一個N×N的白色棋盤，但其中左上到右下的對角線上所有格子都被塗成黑色，如下圖。

有一個古老的遊戲是，拿著棋子從左上角開始，每次只能往右或往下移動一格，最後移到右下角為止，而你獲得的分數就是經過的黑色格子數量（起、終點都算）。當然，這個遊戲看起來十分的無聊，因此聰明的小明決定試著把所有符合規則的不同路徑全部各玩過一次。

小明很好奇當他玩完所有的可能的路徑之後，他每一局的分數全部加起來會是多少。但是因為路徑實在是太多了，所以他只想知道分數總和mod109+7的結果。你可以寫個程式幫他計算嗎？

Input Format

輸入第一行有一個正整數T，代表測資筆數。
接下來T行，每行包含一個正整數N，代表詢問大小為N的方陣。

Output Format

對於每筆測資，請輸出一行包含一個正整數，代表分數總和mod109+7的結果。

Sample Input 1

2
2
1

Sample Output 1

4
1

Hints

請試著只用int完成這題。

Problem Source

Problem by Paupière

Subtasks

No. Testdata Range Constraints Score
1 0~1 T≤5，N≤10 5
2 0~4 T≤5，N≤1000 20
3 0~6 T≤5，N≤106 25
4 0~8 T≤105，N≤109 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 262144 262144 1 2 3 4
1 2000 262144 262144 1 2 3 4
2 2000 262144 262144 2 3 4
3 2000 262144 262144 2 3 4
4 2000 262144 262144 2 3 4
5 2000 262144 262144 3 4
6 2000 262144 262144 3 4
7 2000 262144 262144 4
8 2000 262144 262144 4
Submit
Back to Top