TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

75.0% (3/4)

Submission's AC Ratio

54.2% (13/24)

Tags

Description

建康中學(簡稱建中)是傳說中的「千湖中學」。建中的三年級學生們要畢業了,畢籌會正計劃著做一件「大事」--在學校內造一個大大的水坑。

為了達成目的,畢籌會決定蓋一條由$2m$段路連接起來的路徑,將兩個高度為$n$的高地連接起來,且這條路徑的正中間的高度為0. 如此一來,這條路徑就變成了一個碗狀,暴雨來襲時就會形成超級巨大的水坑。

美觀起見,畢籌會決定讓這條路是對稱的,所以如果要決定整個路徑的形狀,畢籌會只需要考慮從某一端的高地到中間的低地的路徑應該要長怎樣。假設這一段路徑中,第一段路的高度降低了$a_1$, 第二段路的高度降低了$a_2$, 以此類推,其中$a_1,a_2,\ldots,a_m$都是正整數。不難發現$a_1, a_2, \ldots, a_m$應該要滿足限制條件$a_1+a_2+\cdots +a_m = n$. 除此之外,為了希望這個路徑看起來像個碗狀,畢籌會希望$a_1\geq 2a_2, a_2\geq 2a_3, \ldots, a_{m-1} \geq 2a_m$.

請問畢籌會有幾種方法蓋出這條路徑?

Input Format

每組測資只包含一行,含有兩個正整數$n<2^ {20} -1, m\leq 20$, 分別代表兩端高地以及中央低地的高度差以及某端高地至中央低地要由幾段路連接。

子任務(測資) 額外限制 分數
1 (0~4) $n\leq 15$ 10
2 (5~9) $n\leq 1000$ 40
3 (0~14) 50

Output Format

請輸出一個正整數,代表可行的方案個數。由於答案可能很大,請將答案模1000000007後輸出。

Sample Input

10 3

Sample Output

2

Hints

範例測資中,$7+2+1$以及$6+3+1$都是可行的方案。

Problem Source

Problem/Description by Paupière.
改編自2017 APMO P3.

Subtasks

No. Testdata Range Score
1 0~4 10
2 5~9 40
3 10~14 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 1
4 1000 65536 262144 1
5 1000 65536 262144 2
6 1000 65536 262144 2
7 1000 65536 262144 2
8 1000 65536 262144 2
9 1000 65536 262144 2
10 50 65536 262144 3
11 50 65536 262144 3
12 50 65536 262144 3
13 50 65536 262144 3
14 50 65536 262144 3