問題概略
X, Y, Zの 3 種類の文字を並べて長さが5の文字列を作ります。
X と Y が隣同士に並ばないような文字列は全部で何通り作ることができるでしょうか。たとえば XXXXX, XXZYZ は条件をみたしますが XZYYX は条件をみたしません。
解説の pdf も作りました。きれいなレイアウトで読みたい方はこちらをどうぞ。
漸化式を立てる
文字並べたとき最後が X, Y, Z のものが
,
,
個あるとします。漸化式は次のようになります。
\begin{array}{l} x_1=y_1=z_1=1\\
x_{n}=x_{n-1}+z_{n-1}\\
y_{n}=y_{n-1}+z_{n-1}\\
z_{n}=x_{n-1}+y_{n-1}+z_{n-1}\mbox{ ……(1)}
\end{array}
この漸化式を使って を求めればそれが答えですが，もう少し扱いやすい形に直してから計算したいと思います。
とおいて
を求めます。
(1)の漸化式を辺ごとに足して などを使うと
だけの式が作れます。
\begin{align*}
f_{n}&=x_n+y_n+z_n\\
&=2(x_{n-1}+y_{n-1}+z_{n-1})+z_{n-1}\\
&=2f_{n-1}+f_{n-2}\mbox{ ……(2)}
\end{align*}
,
もわかります。これを繰り返し使うと解けます。99 通りです。
n が非常に大きかったら？
プログラムを組んで非常に大きい に対して解を高速に求める方法について書きます。
置換で書く
が非常に大きいとき(1)や(2)は時間がかかりすぎるだけでなく，言語によっては再帰の回数が多すぎてエラーになってしまうので再帰を使わずに書きます。
X と Y は対等なので は明らかで，(1)は
,
だけの式に直せます。
\begin{array}{l}
x_1=z_1=1\\
x_{n}=x_{n-1}+z_{n-1}\\
z_{n}=2x_{n-1}+z_{n-1}=2x_{n}-z_{n-1}
\end{array}
,
の置換を繰り返して，最後に
を求めます。
競技プログラミングによくある「 で割った余り」を求める形で書いてみました。
で約 1.4 秒でした。
In[]:= AbsoluteTiming[
x = 1; z = 1;
mod = 10^9 + 7;
Do[x = Mod[x + z, mod]; z = Mod[2 x - z, mod], {n, 10^6 - 1}];
ans = Mod[2 x + z, mod]]
Out[]= {1.37417, 400591637}
繰り返し二乗法を使う
(2)の漸化式を行列で書きます。
\begin{align*}
&\begin{pmatrix}f_n\\ f_{n-1}\end{pmatrix}
=\begin{pmatrix}2f_{n-1}+f_{n-2}\\ f_{n-1}\end{pmatrix}
=\begin{pmatrix}2&1\\1&0\end{pmatrix}
\begin{pmatrix}f_{n-1}\\f_{n-2}\end{pmatrix}\\
&\therefore \begin{pmatrix}f_n\\ f_{n-2}\end{pmatrix}
=\begin{pmatrix}2&1\\1&0\end{pmatrix}^{n-2}
\begin{pmatrix}f_{2}\\f_{1}\end{pmatrix}
=\begin{pmatrix}2&1\\1&0\end{pmatrix}^{n-2}
\begin{pmatrix}7\\3\end{pmatrix}
\end{align*}
乗の計算に MatrixPowerMod を使うと，繰り返し二乗法で処理してくれます。
の計算が約
回で終わって約
秒で答えが出ます。
In[]:= AbsoluteTiming[
m = {{2, 1}, {1, 0}};
mod = 10^9 + 7;
ans = First@Algebra`MatrixPowerMod[m, 10^6 - 2, mod] . {7, 3};
ans = Mod[ans, mod]]
Out[]= {0.0001012, 400591637}
