問題一覧 > 通常問題

No.940 Warp ε=ε=ε=ε=ε=│;p>д＜│

レベル : / AI推定難易度 : 2400 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 49
作問者 : 37zigen / テスター : CuriousFairy315
お気に入りにしたユーザー ProblemId : 3679 / 自分の提出
問題文最終更新日: 2019-12-03 17:51:08
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2019 (順位表) の他の問題:

Problem Statement

In the year 20XX, Yuki-bako-kun (the logo at the top left) vanished from yukicoder.
A runaway artificial intelligence gave Yuki-bako-kun a mind of its own, and it fled from yukicoder.

For any non-negative integers $a,b,c,x,y,z$ with $(a,b,c)\neq \mathbf{0}$, Yuki-bako-kun can warp from coordinates $(x,y,z)$ to coordinates $(x+a,y+b,z+c)$.
Count the number of paths from the origin $(0,0,0)$ to $(X,Y,Z)$, modulo $\bmod 10^9+7$.

Input

$X$ $Y$ $Z$

$X,Y,Z\in\mathbb{Z}$
$0\leq X\leq10^5$
$0\leq Y\leq10^5$
$0\leq Z\leq10^6$

Output

Print a newline at the end.

Sample

Sample 1
Input
1 1 0
Output
3

$(0,0,0)\to(1,1,0)$
$(0,0,0)\to(1,0,0)\to(1,1,0)$
$(0,0,0)\to(0,1,0)\to(1,1,0)$
These are the $3$ paths.

Sample 2
Input
1 1 1
Output
13
By Sample 1, there are $9$ paths that pass through one of $(1,1,0),(1,0,1),(0,1,1)$.
The other paths are
$(0,0,0)\to(1,1,1)$
$(0,0,0)\to(1,0,0)\to(1,1,1)$
$(0,0,0)\to(0,1,0)\to(1,1,1)$
$(0,0,0)\to(0,0,1)\to(1,1,1)$
which make $4$ paths. Therefore there are $13$ paths in total.

Sample 3
Input
10 0 0
Output
512

Each of $(1,0,0),(2,0,0),\ldots,(9,0,0)$ is either passed through or not, giving $2^9=512$ paths.

Sample 4
Input
31 53 6000
Output
882313923

Remember to take the result mod $10^9+7$.

Sample 5
Input
0 0 0
Output
1

Yuki-bako-kun stays at the origin.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。