[TIOJ] 1331. 索拉數列
題目連結: http://tioj.infor.org/problems/1331 看一眼大概就可以發現這就是一個經典的矩陣優化DP的題目，稍微算一下後得到轉移矩陣$ \begin{bmatrix} 0 & x \\ 1 & y \\ \end{bmatrix} $，所以要求$a_n$其實就是算$ \begin{bmatrix} a_0 & a_1 \\ \end{bmatrix} \times \begin{bmatrix} 0 & x \\ 1 & y \\ \end{bmatrix}^n = \begin{bmatrix} a_n & a_{n+1} \\ \end{bmatrix}$ ，然後冪次的部分用快速冪解決。 #include <bits/stdc++.h>
using namespace std;
typedef long long lld;
typedef unsigned long long llu;
const llu mod = 1LL<<32;
auto A = new llu[2][2];
auto B = new llu[2][2];
auto C = new llu[2][2];
auto F = new llu[2][2];
void mTimes(llu[2][2],llu[2][2],llu[2][2],int,int,int);
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
lld n, a, b, x, y;
while(cin>>n, n>=0){
cin>>a>>b>>x>>y;
F[0][0]=a;
F[0][1]=b;
A[0][0]=0;
A[0][1]=x;
A[1][0]=1;
A[1][1]=y;
B[0][0]=...