No.2033 Chromatic Duel
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 34
作問者 :
Shirotsume
/ テスター :
👑
ygussany
とりゐ
タグ : / 解いたユーザー数 34
作問者 :

問題文最終更新日: 2022-08-09 12:44:06
問題文
左右方向に 個のマス目が並んだ盤面があります。初め、各マス目には何も置かれていません。
この盤面に対し、先手と後手が以下の操作を行います。
- 先手が 個のマス目から 個の異なるマス目を選び、それぞれに黒い駒を つずつ置く。
- 後手が下記のルールに従って盤面に白い駒を置く。
- つのマス目に置かれる駒は、白い駒と黒い駒を合わせて高々 つ。
- 黒い駒が置かれているマスと左右に隣接したマスには白い駒を置いてはならない。同じ色の駒同士は隣接していても構わない。
後手が置く白い駒の個数として考えられる最大値は、先手の駒の置き方に依存します。
先手が黒い駒を置く方法は 通りありますが、このうち後手が置く白い駒の個数として考えられる最大値がちょうど となるものは何通りあるでしょうか?この答えを で割ったあまりを求めてください。
制約
- 入力はすべて整数
入力
入力は標準入力から以下の形式で与えられる。
出力
答えを出力せよ。最後に改行すること。
サンプル
サンプル1
入力
4 1 1
出力
2
次に示す 通りです。以下に、それぞれについて両者の操作が終わった後の盤面の状態を示します。黒い駒が置かれたマスを x
、何も置かれていないマスを .
として表します。
.x..
..x.
先手が x...
という並べ方をした場合、後手は x.oo
のように つの白い駒を並べることができるので、問題の条件に反します。
サンプル2
入力
6 2 1
出力
6
次に示す 通りです。
x..x..
.x.x..
x...x.
..x.x.
.x...x
..x..x
サンプル3
入力
5 3 0
出力
8
次に示す 通りです。
xx.x.
xx..x
x.xx.
x.x.x
x..xx
.xxx.
.xx.x
.x.xx
サンプル4
入力
200000 123456 67890
出力
400954588
で割ったあまりを出力してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。