[ARC061F] 3人でカードゲーム
题意翻译
三人 $a,b,c$ 面前分别有 $N, M, K$ 张牌,每张牌上写了 $a,b,c$ 中的一个, 规则如下:
第一回合是 $a$ 的回合,若轮到某个玩家行动时他面前没牌了,该玩家获胜。
否则拿出牌堆顶的一张牌,丢掉它,并进入该牌上写着的玩家的回合。
游戏开始前牌的所有情况共 $3^{n+m+k}$ 种。
求 $a$ 获胜的情况数。
对 $10^9+7$ 取模。
感谢@YJMSTR 提供的翻译
题目描述
[problemUrl]: https://atcoder.jp/contests/arc061/tasks/arc061_d
A さん、B さん、C さんの $ 3 $ 人が以下のようなカードゲームをプレイしています。
- 最初、$ 3 $ 人はそれぞれ `a`、`b`、`c` いずれかの文字が書かれたカードを、A さんは $ N $ 枚、B さんは $ M $ 枚、C さんは $ K $ 枚持っている。$ 3 $ 人は、持っているカードを並べ替えることはできない。
- A さんのターンから始まる。
- 現在自分のターンである人がカードを $ 1 $ 枚以上持っているならば、そのうち先頭のカードを捨てる。その後、捨てられたカードに書かれているアルファベットと同じ名前の人 (例えば、カードに `a` と書かれていたならば A さん) のターンとなる。
- 現在自分のターンである人がカードを $ 1 $ 枚も持っていないならば、その人がゲームの勝者となり、ゲームは終了する。
$ 3 $ 人が最初に配られるカードに書いてある文字の並びは、全部で $ 3^{N+M+K} $ 通りの組み合わせがあります。このうち、A さんが勝者となってゲームが終了するのが何通りあるかを求めてください。
答えは大きくなる可能性があるので、$ 1\,000\,000\,007\ (=10^9+7) $ で割った余りを出力してください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ M $ $ K $
输出格式
答えを $ 1\,000\,000\,007\ (=10^9+7) $ で割った余りを出力せよ。
输入输出样例
输入样例 #1
1 1 1
输出样例 #1
17
输入样例 #2
4 2 2
输出样例 #2
1227
输入样例 #3
1000 1000 1000
输出样例 #3
261790852
说明
### 制約
- $ 1\ \leq\ N\ \leq\ 3×10^5 $
- $ 1\ \leq\ M\ \leq\ 3×10^5 $
- $ 1\ \leq\ K\ \leq\ 3×10^5 $
### 部分点
- $ 1\ \leq\ N\ \leq\ 1000 $、 $ 1\ \leq\ M\ \leq\ 1000 $、 $ 1\ \leq\ K\ \leq\ 1000 $ を満たすデータセットに正解した場合は、 $ 500 $ 点が与えられる。
### Sample Explanation 1
\- A さんが `a` を持っている場合は、他の $ 2 $ 人の持っているカードに関わらず A さんが勝ちます。これは $ 3×3=9 $ 通りあります。 - A さんが `b` を持っている場合は、B さんが `a` を持っているか、 B さんが `c` を持っていてかつ C さんが `a` を持っている場合に限り A さんが勝ちます。これは $ 3+1=4 $ 通りあります。 - A さんが `c` を持っている場合は、C さんが `a` を持っているか、 C さんが `b` を持っていてかつ B さんが `a` を持っている場合に限り A さんが勝ちます。これは $ 3+1=4 $ 通りあります。 合計すると、 $ 9+4+4=17 $ 通りとなります。