No.621 3 x N グリッド上のドミノの置き方の数

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 31
作問者 :

しらっ亭 / テスター :

roiti46

2 ProblemId : 2031 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2017-12-17 22:48:43

縦に $3$ 個、横に $N$ 個のマス目からなるグリッドを $3 \times N$ のグリッドと呼ぶ。
下記の図は、 $3 \times 10$ のグリッドである。

「 $3 \times N$ のグリッドのマス目の上に、 $1 \times 2$ サイズのドミノを、ドミノ同士が重ならないように、ドミノがグリッドからはみ出さないように、これ以上置けなくなるまで置く方法」の総数を $10^{9} + 7$ で割った余りを求めよ。

ドミノは回転して使ってよい。それぞれのドミノは区別しない。
グリッドをドミノで埋め尽くす必要が無い点に注意せよ。

$N$

$1 \leq N \leq 10^{18}$
$N$ は整数

答えを1行で出力せよ。
最後に改行せよ。

の $5$ 通りである。

等は、まだドミノを置くことができるため、数えない。

718700373

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