D問題を時間内に解けなかった＆考えていた方法が想定解と違っていたので供養する。
問題ページ：https://atcoder.jp/contests/abc122/tasks/abc122_d
スマートな（？）漸化式を立てる
\[S_n:=\{\text{ACGTからなる長さ\(n\)の文字列で、問題文の条件を満たすもの}\}\]とおく。ただし、問題文の条件とは、「AGC を含まない＆1文字並び替えても AGC を含まない」であった。
問題文の条件を言い換えると、部分文字列として以下のものを含まない、となる：
AGCGACACGATGCAGTCAGGC
（4文字の「含んではいけない文字列」に関しては * を任意の文字として A*GC, AG*C と書けるが、 ATGC, AGTC, AGGC 以外のパターンはいずれも「3文字の含んではいけない文字列」を部分文字列として含むため、重複を避ける意味で除外した。例：A*GC で *=C とした ACGC は部分文字列として ACG を含む）
大きな\(n\)に対して\(S_n\)（の要素数）を求めたいわけだが、いきなり求めるのは難しいので漸化式を考える。
初期値として、\(n<0\)の時は\(S_n=\emptyset\), \(n=0\)の時は\(S_0=\{\varepsilon\}\)（長さ0の文字列のみからなる要素数1の集合）である。
\(n\ge1\)について、\(S_n\) の元は \(S_{n-1}\) の先頭に1文字付け加えた形をしている。ただし、先頭に付け加えることによって「含んではいけない文字列」が出現してはいけない。数式っぽく書けば次のようになる：
\begin{align*}
S_n&=\{cs\mid c\in\{\mathtt{A},\mathtt{C},\mathtt{G},\mathtt{T}\},s\in S_{n-1}\}\\
&\quad\setminus\{\mathtt{AGC}t\mid t\in S_{n-3}\}\\
&\quad\setminus\{\mathtt{GAC}t\mid t\in S_{n-3}\}\\
&\quad\setminus\{\mathtt{ACG}t\mid t\in S_{n-3}\}\\
&\quad\setminus\{\mathtt{ATGC}u\mid u\in S_{n-4}\}\\
&\quad\setminus\{\mathtt{AGTC}u\mid u\in S_{n-4}\}\\
&\quad\setminus\{\mathtt{AGGC}u\mid u\in S_{n-4}\}
\end{align*}
求めたいのは集合の要素数なので、集合演算を集合の要素数に関する演算に読み替えてやれば良いのだが、注意点がある。
というのは、\(\{cs\mid c\in\{\mathtt{A},\mathtt{C},\mathtt{G},\mathtt{T}\},s\in S_{n-1}\}\)（以後これを\(U\)とおく）から引いている\(\{\mathtt{GAC}t\mid t\in S_{n-3}\}\)と\(\{\mathtt{ACG}t\mid t\in S_{n-3}\}\)は（一般には）\(U\)の部分集合ではない。
例えば、GACG (\(n=4\)) を考えるとACGは\(S_{n-1}\)の元ではないのでGACGは\(U\)には含まれないが、Gは\(S_{n-3}\)に含まれるのでGACGは\(\{\mathtt{GAC}t\mid t\in S_{n-3}\}\)に含まれる。
同様に、ACGAC (\(n=5\)) を考えると、CGACは\(S_{n-1}\)の元ではないのでACGACは\(U\)に含まれないが、ACは\(S_{n-3}\)に含まれるのでACGACは\(\{\mathtt{ACG}t\mid t\in S_{n-3}\}\)に含まれる。
この問題を解消するには、「\(\{\mathtt{GAC}t\mid t\in S_{n-3}\}\)の\(t\)はGから始まらない」「\(\{\mathtt{ACG}t\mid t\in S_{n-3}\}\)の\(t\)はACから始まらない」という条件をつければ良い。そこで、\begin{align*}S^{\mathtt{AC}}_n&=\{s\in S_n\mid s\text{はACから始まる}\},\\S^{\mathtt{G}}_n&=\{s\in S_n\mid s\text{はGから始まる}\}\end{align*}とおき、\(S_n\)の漸化式を\begin{align*}
S_n&=\{cs\mid c\in\{\mathtt{A},\mathtt{C},\mathtt{G},\mathtt{T}\},s\in S_{n-1}\}\\
&\quad\setminus\{\mathtt{AGC}t\mid t\in S_{n-3}\}\\
&\quad\setminus\{\mathtt{GAC}t\mid t\in S_{n-3}\setminus S^{\mathtt{G}}_{n-3}\}\\
&\quad\setminus\{\mathtt{ACG}t\mid t\in S_{n-3}\setminus S^{\mathtt{AC}}_{n-3}\}\\
&\quad\setminus\{\mathtt{ATGC}u\mid u\in S_{n-4}\}\\
&\quad\setminus\{\mathtt{AGTC}u\mid u\in S_{n-4}\}\\
&\quad\setminus\{\mathtt{AGGC}u\mid u\in S_{n-4}\}
\end{align*}とすれば、「引く側は常に引かれる側の部分集合である」という条件を満たすようにできる。つまり、集合の差の要素数を、引かれる側と引く側の要素数の差で計算できる（\(\#(A\setminus B)=\#A-\#B\)という感じ）。
\(S^{\mathtt{AC}}_n\)と\(S^{\mathtt{G}}_n\)の初期値はいずれも\(\emptyset\) (\(n\le 0\)) で、\(n\ge1\)での漸化式はそれぞれ\begin{align*}
S^{\mathtt{AC}}_n&=\{\mathtt{AC}s\mid s\in S^{n-2}\setminus S^{\mathtt{G}}_{n-2}\},\\
S^{\mathtt{G}}_n&=\{\mathtt{G}s\mid s\in S^{n-1}\setminus S^{\mathtt{AC}}_{n-1}\}
\end{align*}となる。
あとは、集合の要素数についての漸化式に変換すれば良い。
それぞれの集合の要素数を\(a_n:=\#S_n\), \(b_n:=\#S^{\mathtt{AC}}_n\), \(c_n:=\#S^{\mathtt{G}}_n\)とおく。入力\(n\)に対して\(a_n\)が計算すべき値である。\(a_n\), \(b_n\), \(c_n\)の初期値は\begin{align*}
a_n&=\begin{cases}1 & (n=0)\\0&(n<0)\end{cases}\\
b_n&=0\quad(n\le0)\\
c_n&=0\quad(n\le0)
\end{align*}で、\(n\ge1\)での漸化式は\begin{align*}
a_n&=4a_{n-1}-a_{n-3}-(a_{n-3}-c_{n-3})-(a_{n-3}-b_{n-3})-3a_{n-4} \\
&=4a_{n-1}-3a_{n-3}-3a_{n-4}+b_{n-3}+c_{n-3}, \\
b_n&=a_{n-2}-c_{n-2}, \\
c_n&=a_{n-1}-b_{n-1}
\end{align*}である。
この漸化式の、Haskellでの実装例は次のようになる：
-- N は mod 10^9+7 で計算する整数型
solution :: [(N,N,N)]
solution = (1,0,0) : zipWith4 (\(a1,b1,c1) (a2,b2,c2) (a3,b3,c3) (a4,b4,c4) -> (4*a1-3*a3-3*a4+b3+c3,a2-c2,a1-b1)) solution ((0,0,0):solution) (replicate 2 (0,0,0) ++ solution) (replicate 3 (0,0,0) ++ solution)
試しに take 10 してみると
> take 10 solution
[(1,0,0),(4,0,1),(16,1,4),(61,3,15),(230,12,58),(865,46,218),(3247,172,819),(12185,647,3075),(45719,2428,11538),(171531,9110,43291)]
となる。リストの最初が\(n=0\)に相当する。欲しい答え\(a_n\)はタプルの最初の要素で、\(n=3\)の場合は61、\(n=4\)の場合は230と、うまく計算できていることがわかる（問題ページに例としてこれらの値がある）。
\(n=100\)の場合も計算してみると、
> solution !! 100
(388130742,386628627,667222078)
と、正しい答え 388130742 が得られる。
漸化式としては、3変数の5項間漸化式という、結構大掛かりなものになった。
このアルゴリズムを実装して提出した結果がこれである：
提出 #4704278 – AtCoder Beginner Contest 122
残念ながらコンテストの時間内には間に合わなかった。
想定解との比較
想定解（公式で解説されているアルゴリズム）は、要素数\(4\times4\times 4\)の配列をDPの状態として持って回る（DPの状態を一つの大きな配列に入れるなら、要素数は\(4\times 4\times 4\times (N+1)\)）ようなアルゴリズムである。
これもHaskellで実装してみた：
提出 #4704760 – AtCoder Beginner Contest 122
比較すると、「新しい状態を計算する際に参照する以前の状態」は、想定解では要素数\(4^3=64\)の配列、この記事に書いた解では3要素タプルが4つ（合計12個）である。
よって、この記事に書いたアルゴリズムの方が想定解よりもメモリ消費量が少ない。多分計算量もこっちの方が定数倍で少ないと思うが、どっちにしろ O(N) である。
行列の冪乗を使う
さて、N=100程度なら O(N) のアルゴリズムで十分だが、Nがもっと大きかったらどうするか。というわけで、 O(log N) のアルゴリズムも検討しておこう。
せっかく線形漸化式を立てたので、行列の冪乗を使って高速化しよう。さっき書いた漸化式を、行列を使って書くと次のようになる：
\[\begin{pmatrix}a_n\\a_{n-1}\\a_{n-2}\\a_{n-3}\\b_n\\b_{n-1}\\b_{n-2}\\c_n\\c_{n-1}\\c_{n-2}\end{pmatrix}=\begin{pmatrix}4&0&-3&-3&0&0&1&0&0&1\\1&0&0&0&&&&&&\\0&1&0&0&&&&&&\\0&0&1&0&&&&&&\\\hline0&1&0&0&0&0&0&0&1&0\\&&&&1&0&0&&&\\&&&&0&1&0&&&\\\hline1&0&0&0&1&0&0&0&0&0\\&&&&&&&1&0&0\\&&&&&&&0&1&0\end{pmatrix}\begin{pmatrix}a_{n-1}\\a_{n-2}\\a_{n-3}\\a_{n-4}\\b_{n-1}\\b_{n-2}\\b_{n-3}\\c_{n-1}\\c_{n-2}\\c_{n-3}\end{pmatrix}\]
ベクトルの初期値は\(\begin{pmatrix}a_0\\a_{-1}\\a_{-2}\\a_{-3}\\b_0\\b_{-1}\\b_{-2}\\c_0\\c_{-1}\\c_{-2}\end{pmatrix}=\begin{pmatrix}1\\0\\0\\0\\0\\0\\0\\0\\0\\0\end{pmatrix}\)であり、\(a_n\)を得るには行列の\(n\)乗をこのベクトルに乗じてやれば良い。
それにしても……でかい。もう少し行列を小さくできないものか。
漸化式を多少いじると、\begin{align*}
a_n&=4a_{n-1}-2a_{n-3}-3a_{n-4}-b_{n-1}+b_{n-3}\\
b_n&=a_{n-2}-a_{n-3}+b_{n-3}
\end{align*}という風に\(c_n\)を消去できる。これを行列で書くと少し小さくなり、\[
\begin{pmatrix}a_n\\a_{n-1}\\a_{n-2}\\a_{n-3}\\b_n\\b_{n-1}\\b_{n-2}\end{pmatrix}=\begin{pmatrix}4&0&-2&-3&-1&0&1\\1&0&0&0&&&\\0&1&0&0&&&\\0&0&1&0&&&\\\hline 0&1&-1&0&0&0&1\\&&&&1&0&0\\&&&&0&1&0\end{pmatrix}\begin{pmatrix}a_{n-1}\\a_{n-2}\\a_{n-3}\\a_{n-4}\\b_{n-1}\\b_{n-2}\\b_{n-3}\end{pmatrix}
\]という風に\(7\times 7\)行列となる。
この方法で行列演算に持ち込み、冪乗を log N で計算したコード（の提出結果）が次である：
提出 #4709903 – AtCoder Beginner Contest 122
まあ N=100 程度では取り立てて面白いものではない。手元で実行して大きな N を与えてみよう。
多項式除算を使う
このあいだの記事
に書いたように、行列の特性多項式がわかっていれば多項式除算によって行列の冪乗を高速に計算できる。
今回は線形漸化式とは言っても変数が複数あるため、フィボナッチ数の時のように直ちに特性多項式がわかるというわけではない。
が、使う行列は固定なので、数式処理ソフトでも使って特性多項式を計算してやれば良い。
Maximaによると、さっきの\(7\times 7\)行列の特性多項式は\[P(X)=-X^7+4X^6-2X^4-6X^3+X^2+X+3\]である（Maximaが計算する特性多項式は最高次の係数が正とは限らないらしい）。よって、多項式\(X^N\bmod P(X)\)を計算してから\(X\)に行列を代入してやれば行列を直接冪乗せずに済む。
と言っても、TDPC-Tの時と違って行列のサイズが固定なので、行列を直接冪乗するのと多項式除算を使うのとでは定数倍しか変わらない。
一応実装して提出してみたが、やはりN=100程度では目に見える違いはない。
提出 #4710308 – AtCoder Beginner Contest 122
