[AGC009E] Eternal Average
题意翻译
黑板上有 $n$ 个 $0$ 和 $m$ 个 $1$,我们每次选择 $k$ 个数字将其擦除,然后把它们的平均数写上去,这样一直操作直到只剩下一个数字,问剩下的这个数字有多少种不同的情况。
答案对 $10^9+7$ 取模。
$1 \leq n,m \leq 2000,2 \leq k \leq 2000$
保证 $n+m-1$ 能被 $k-1$ 整除。
题目描述
[problemUrl]: https://atcoder.jp/contests/jrex2017/tasks/agc009_e
黒板に、$ N $ 個の $ 0 $ と $ M $ 個の $ 1 $ が書かれています。 この状態から、黒板に書かれている有理数のうち $ K $ 個を選んで消し、それら $ K $ 個の有理数の平均を新たに書き加える操作を繰り返します。 ただし、$ N+M-1 $ は $ K-1 $ で割り切れるものとします。
このとき、操作ができなくなるまでこの操作を繰り返すと最終的に黒板には $ 1 $ つの有理数が書かれた状態になります。
この残った有理数の値としてありうるものの個数を $ 10^9\ +\ 7 $ で割ったあまりを求めてください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ M $ $ K $
输出格式
最後に残った有理数の値としてありうるものの個数を $ 10^9\ +\ 7 $ で割ったあまりを出力せよ。
输入输出样例
输入样例 #1
2 2 2
输出样例 #1
5
输入样例 #2
3 4 3
输出样例 #2
9
输入样例 #3
150 150 14
输出样例 #3
937426930
说明
### 制約
- $ 1\ ≦\ N,\ M\ ≦\ 2000 $
- $ 2\ ≦\ K\ ≦\ 2000 $
- $ N+M-1 $ は $ K-1 $ で割り切れる。
### Sample Explanation 1
最後に残る有理数としてありうるものは、$ \frac{1}{4},\ \frac{3}{8},\ \frac{1}{2},\ \frac{5}{8},\ \frac{3}{4} $ の $ 5 $ 通りです。 例えば $ \frac{3}{8} $ は、以下のような操作で最後に残ります。 - $ 0,1 $ を消して $ \frac{1}{2} $ を書く。 - $ \frac{1}{2},1 $ を消して $ \frac{3}{4} $ を書く。 - $ 0,\frac{3}{4} $ を消して $ \frac{3}{8} $ を書く。