問題一覧 > 通常問題

No.175 simpleDNA

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 433
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm
1 ProblemId : 415 / 出題時の順位表
問題文最終更新日: 2017-06-25 00:53:47

問題文

A君はとても単純なDNAで知られるsimpleDNAの研究をしています。
simpleDNAの特徴は次のようなものです。

・simpleDNAは普通のDNAと同じく分岐しない塩基配列を持ちます。
・simpleDNAはとてもシンプルなので'A'と'B'の2種の塩基で構成されています。
・simpleDNAはとてもシンプルなので塩基配列の長さはせいぜい30までです。
・simpleDNAの塩基配列の長さはかならず3の倍数です。

このようなsimpleDNAからA君は次のようなsimpleDNAを探しています。

・塩基配列の末端が指定された終止コドンで終わるもの。

コドンとは3つの塩基配列の組み合わせのことを言います。
要は、最後の3つの塩基配列が終止コドンとして指定されるということです。
長さ$L$と候補の終止コドンがいくつか指定されます。
このような条件を満たすsimpleDNAは何パターンありうるでしょうか?

※なお、普通のDNAについての説明はこちらをご覧ください。
http://en.wikipedia.org/wiki/DNA

入力

$L$
$N$
$S_1\ S_2\ \dots\ S_n$

$L$はsimpleDNAの塩基配列の長さです。$3\le L \le 30$。($L$は3の倍数。)
$N$は終止コドンの候補の数です。$1\le N \le 8$。
$S_i$は$i$番目の終止コドンの候補です。
$S_i$は必ず'A'または'B'で構成される3文字の文字列です。
終止コドンの候補には複数同じものが含まれません。

出力

A君が見つけることのできるsimpleDNAの配列のパターン数を1行で出力せよ。
最後に改行を忘れずに。

サンプル

サンプル1
入力
6
1
AAB
出力
8

最後が「AAB」で終わる長さ6のsimpleDNAを探します。
「AAAAAB」、「AABAAB」、「ABAAAB」、「ABBAAB」、「BAAAAB」、「BABAAB」、「BBAAAB」、「BBBAAB」
の8つが見つかります。

サンプル2
入力
3
3
AAA BBB BAB
出力
3

最後が「AAA」、「BBB」もしくは「BAB」で終わる長さ3のsimpleDNAを探します。
この条件を満たすのは「AAA」、「BBB」、「BAB」の3つしかありません。

サンプル3
入力
18
5
AAA AAB ABB BAA BBA
出力
163840

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