上篇博客就是在写这篇题解的时候发现公式预览不好用弄出来的23333
题目链接:https://codeforces.com/contest/1182/problem/E
题目大意:
定义一个函数
$f_x=c^{2x-6}*f_{x-1}*f_{x-2}*f_{x-3}$ for $x\geq4$ , $f_1,f_2,f_3$是已知的,求$f_nmod(1e9+7)$
思路
乍一看感觉是矩阵快速幂,但是递推关系不是线性的没法写呀,然后我们可以发现每一项的指数是满足线性递推关系的
$f_4=c^2 \cdot f_1 \cdot f_2 \cdot f_3$
$f_5=c^{4+2} \cdot f_1 \cdot f_2^2 \cdot f_3^2$
$f_5=c^{6+6+2} \cdot f_1^2 \cdot f_2^3 \cdot f_3^4$
a然后不难看从$f_6$之后$f_1,f_2,f_3$的指数都是前三项的和,设$f_n$中的$f_1$的指数是$t_n$,则$$t_n=t_{n-1}+t_{n-2}+t_{n-3}$$
$f_2,f_3$的指数同理,这就可以构建一个矩阵了
$$\begin{pmatrix}
{t_{n-3}}&{t_{n-2}}&{t_{n-1}}
\end{pmatrix} \begin{pmatrix} 0&0&1\\ 1&0&1\\ 0&1&1\end{pmatrix}
\begin{pmatrix} t_{n-2}&t_{n-1}&t_n \end{pmatrix}$$
且$f_1$的$t_1=1,t_2=1,t_3=2$$f_2$的$t_1=1,t_2=2,t_3=3$$f_3$的$t_1=1,t_2=1,t_3=4$
然后是$C$的指数,设$C$的指数是$k$,则从$f_4$开始算$k_1=2,k_2=6,k_3=14$
$$k_n=k_{n-1}+k_{n-2}+k_{n-3}+2 \cdot n$$
即
$$k_n=k_{n-1}+k_{n-2}+k_{n-3}+2 \cdot (n-1)+2$$
构造矩阵:
$$\begin{pmatrix}
{k_{n-3}}&{k_{n-2}}&{k_{n-1}}&{2 \cdot (n-1)}&{2}
\end{pmatrix} \begin{pmatrix} 0&0&1&0&0\\ 1&0&1&0&0\\ 0&1&1&0&0\\0&0&1&1&0\\ 0&0&1&1&1\end{pmatrix}
\begin{pmatrix} k_{n-2}&k_{n-1}&k_n&2 \cdot n,2 \end{pmatrix}$$
然后矩阵快速幂算的是指数,所以根据欧拉降幂,要对1e9+7的欧拉函数值取模,也就是对1e9+6取模
最后算完指数做快速幂算最后的答案就可以了
AC代码
1 |
|