1331. 索拉數列

連結：https://tioj.ck.tp.edu.tw/problems/1331

題目大意

給定 $a,b,x,y$ 問下遞迴數列第 $n$ 項的數值是多少，取其除以 $2^{32}$ 的餘數：

$$\{\begin{array}{ll}{S}_0& =a\\ S_1& =b\\ S_n& =x{S}_{n-2}+y{S}_{n-1}\end{array}$$

題解

因為 $n$ 的範圍是 ${10}^9$，很顯然的要用矩陣快速冪來計算。矩陣的構造方法就如同費式數列

$${\left[\begin{array}{cc}0& 1\\ x& y\end{array}\right]}^n\left[\begin{array}{c}{S}_0\\ S_1\end{array}\right]=\left[\begin{array}{c}{S}_n\\ S_{n+1}\end{array}\right]$$

利運快速冪來計算可以在 $O(2^3\log n)$ 計算出答案。

AC Code

#include<bits/stdc++.h>
using namespace std;

using u32 = uint32_t;
using matrix = vector<vector<u32>>;
matrix A,T;
//a*=b;
inline void mul(matrix &a, const matrix &b)
{
    //static matrix c(2, vector<u32>(2)); //highlight.js render bug...
    for(int i=0;i<2;++i)
        for(int j=0;j<2;++j)
            c[i][j]=a[i][0]*b[0][j]+a[i][1]*b[1][j];
    a.swap(c);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    u32 n,a,b,x,y;
    while( cin>>n, n<INT_MAX )
    {
        cin>>a>>b>>x>>y;
        
        A = { { 0,1 },
              { x,y } };
        T = { { 1,0 },
              { 0,1 } };
        while( n )
        {
            if( n&1 ) mul(T,A); 
            mul(A,A);
            n/=2;
        }
        
        u32 ans = a*T[0][0] + b*T[0][1];
        cout<<ans<<'\n';
    }
}