递推的四种写法
题目链接
从 MO 搬来的题，难度大概是提高组中的简单题，目的是引进一些基础数学知识。
前置知识：线性递推及各种优化：矩阵加速递推，快速幂，特征方程（高考数学范畴）。
建议先完成：P1902。
题解
环不好处理的地方在于填 \(n\) 时要同时考虑 \(1\) 和 \(n-1\) 。因此先把连接 \(1\) 与 \(n\) 的绳结断开，填好链后再考虑 \(1\) 与 \(n\) 并接成环。
设 \(f_n\)，\(g_n\)，\(h_n\) 分别表示 \(1\) 号与 \(n\) 号豌豆两个性状都相同，一个性状相同，两个性状都不同的方案数，且保证了链是合法的。则 \(n\) 的答案即为 \(f_n+g_n\) 。
列一下初始值（这是一个可能显示不出来的表格）：
| \(n\) | \(1\) | \(2\) | \(3\) | …… |
|---|---|---|---|---|
| \(f_n\) | \(4\) | \(4\) | \(12\) | …… |
| \(g_n\) | \(0\) | \(8\) | \(16\) | …… |
| \(h_n\) | \(0\) | \(0\) | \(8\) | …… |
写一下转移
\[f_n=f_{n-1}+g_{n-1} \]\[g_n=2f_{n-1}+g_{n-1}+2h_{n-1} \]\[h_n=g_{n-1}+h_{n-1} \]综上是 \(40\%\) 的 \(O(n)\) 递推，如果从这里开始 矩乘 ，写的好的话或许也可以有 \(70\%\) ~ \(100\%\) ，如果写的不够漂亮可能会掉到 \(10\%\)。
化简一下式子，不妨从 \(h_n\) 开始。
\[h_n=g_{n-1}+h_{n-1} \]展开 \(h_{n-1}\)，
\[h_n=g_{n-1}+g_{n-2}+h_{n-2} \]\[=g_{n-1}+g_{n-2}+g_{n-3}+h_{n-3} \]设 \(sg_n\) 表示 \(g_n\) 的前 \(n\) 项和，即 \(\sum_{i=1}^ng_i\) ，则
\[h_n=sg_{n-1} \]于是把 \(h\) 消掉了，同理可得
\[f_n=sg_{n-1}+4 \]和 \(h_n\) 不同是因为初始值不同。
那么全部代入 \(g_n\) 里面。
\[g_n=2f_{n-1}+g_{n-1}+2h_{n-1} \]\[=2sg_{n-2}+8+g_{n-1}+2sg_{n-2} \] \[g_n-g_{n-1}=4sg_{n-2}+8 \]化简这个是高考数学玩烂的把戏了，如下：
\[g_n-g_{n-1}=4sg_{n-2}+8 \]\[g_{n-1}-g_{n-2}=4sg_{n-3}+8 \]上式减去下式，得
\[g_n-2g_{n-1}+g_{n-2}=4g_{n-2} \] \[g_n=2g_{n-1}+3g_{n-2} \]斐波那契数列怎么算的，这个就怎么算。
算上 \(sg_n\) 的话（因为要算 \(f_n\) ），这是一个 \(3\times3\) 的矩阵，拿来做 \(70\%\) 再好不过了。
接下来可以运用科技继续化简：
列出特征方程
\[x^2=2x+3 \]解得
\[x_1=3,x_2=-1 \]那么可以设
\[g_n=a\times3^n+b\times(-1)^n \]代入 \(g_1=0,g_2=8\) ，解二元一次方程得 \(a=\dfrac23,b=2\)，即
\[g_n=2\times3^{n-1}+2\times(-1)^n \]由等比数列求和公式，计算 \(sg_n\)
\[sg_n=3^{n}+(-1)^n-2 \]那么
\[f_n=sg_{n-1}+4 \]\[=3^{n-1}+(-1)^{n-1}+2 \]\(n\) 的答案为 \(f_n+g_n\) ，即
\[f_n+g_n=3^n+(-1)^n+2 \]由 费马小定理 ，把 \(n\) 读入的时候直接模 \(P-1\) ，再快速幂就好了。瓶颈在于大量读入，建议用 getchar()。
以上是严格的数学推导，下面是考场的一般做法：
Step 1: 写出暴力搜索，把 n=1~10 的答案跑出来，发现是 4，12，28，84，244……。
Step 2: 观察发现后面和 \(3^n\) 很接近，于是往这方面考虑，得出奇数是 \(3^n+1\)，偶数是 \(3^n+3\)。那么就得到答案了。
这个叫“打表”，是正经做法。
留一道思考题：
\(n\) 元环，\(k\) 染色，相邻点不同色的方案数。答案表示成等比数列形式。
来自 P3307。