题解:洛谷 P1939 矩阵加速（数列）
前置
矩阵知识。
思路
我们设原来的矩阵为
\[\begin{bmatrix}
a_n&a_{n-1}&a_{n-2}
\end{bmatrix}
\]
\(n+1\) 次的矩阵为
\[\begin{bmatrix}
a_{n+1}&a_n&a_{n-1}
\end{bmatrix}
\]
那么，通过题目给的式子
\[a_x=
\begin{cases}1 & x \in\{1,2,3\}\\ a_{x-1}+a_{x-3} & x \geq 4
\end{cases}
\]
可以求出，原来的矩阵乘上 \( \begin{bmatrix} 1&0&1\\ 1&0&0\\ 0&1&0\\ \end{bmatrix} \) 为 \(n+1\) 次的矩阵。而 \(1 \le n \le 2 \times 10^9\) ，所以要用矩阵快速幕。而又因为原来的矩阵是从 \(n=3\) 开始的，所以 \(n\) 要减 \(3\) 。
代码
void operator*=(array<ll,3>&a, array<array<ll,3>, 3>b){array<ll,3>c={};for(int i=0;i<3;i++){for(int j=0;j<3;j++){c[i]=(c[i]+ll(a[j])*b[j][i]%mod)%mod;}}a=c;
}
void operator*=(array<array<ll, 3>,3>&a, array<array<ll,3>, 3>b){for(int i=0;i<3;i++){a[i]*=b;}
}
void solve(){ll n;cin>>n;array<ll,3>a={1, 1, 1};array<array<ll, 3>,3>b={1,0,1,1,0,0,0,1,0};n-=3;for(;n>0;n>>=1){if(n&1){a*=b;}b*=b;}cout<<a[0]<<'\n';
}
本文来自 NoiPLE ，转载请注明原文链接：https://www.cnblogs.com/noiple-dequeee/p/19597010