【hdu 1005 Number Sequence】(循環節 or 矩陣快速幂)

題目連結

利用循環節遞歸

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

#define rep(i,a,n) for(int i=a;i<n;i++)
const int MOD=+;
const int N=+;
typedef long long ll;
typedef long double LDB;
typedef vector<ll>vec;
typedef vector<vec>mat;
int a,b,n;
int fun(int n) {
    if(n==||n==) return ;
    else return (a*fun(n-)+b*fun(n-))%;
}

int main() {
    while(~scanf("%d%d%d",&a,&b,&n),a+b+n) {
        int ans=fun(n%);
        printf("%d\n",ans);
    }
    return ;
}
           

矩陣快速幂：

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

#define rep(i,a,n) for(int i=a;i<n;i++)
const int MOD=+;
const int N=+;
typedef long long ll;
typedef long double LDB;
typedef vector<ll>vec;
typedef vector<vec>mat;
/// 矩陣A * B ,傳回矩陣C
ll a,b,n;
mat mul(mat& A,mat& B) {
    mat C(A.size(),vec(B[].size()));
    for(int i=; i<A.size(); i++) {
        for(int k=; k<B.size(); k++) {
            for(int j=; j<B[].size(); j++) {
                C[i][j] += A[i][k]*B[k][j];
                C[i][j] %= ;
            }
        }
    }
    return C;
}

///計算A^n
mat powMod(mat A,ll n) {
    mat B(A.size(),vec(A.size()));
    rep(i,,A.size()) B[i][i]=;
    while(n) {
        if(n&) B=mul(B,A);
        A=mul(A,A);
        n>>=;
    }
    return B;
}
void solve() {
    mat A(,vec());
    A[][]=a%,A[][]=b%;
    A[][]=,A[][]=;
    A=powMod(A,n-);
    printf("%d\n",(A[][]+A[][])%);
}

int main() {
    while(~scanf("%lld%lld%lld",&a,&b,&n),a+b+n) {
        if(n<) printf("1\n");
        else solve();
    }
    return ;
}