1365 Fib(N) mod Fib(K) [斐波那契相关]

$Fib(N) mod Fib(K)$

Fib(N)表示斐波那契数列的第N项（$F(0) = 0, F(1) = 1$），给出N和K，求 $Fib(N) mod Fib(K)$。由于结果太大，输出 $Mod 1000000007$ 的结果。

---

$color{red}{正解部分}$

首先要知道

$F_i = F_kF_{i-k+1}+F_{k-1}F_{i-k}$,

在 $mod F_k$ 意义下继续化简 $downarrow$

$F_i\ = F_{k-1}F_{i-k}\ = F_{k-1}(F_kF_{i-2k+1}+F_{k-1}F_{i-k-k})\ = F_{k-1}^2F_{i-2k}\ dotsi \ = F_{k-1}^{lfloor frac{i}{k} floor}F_{i\%k}$

---

再要知道

$F_{k-1}^2+F_{k-1}F_{k}-F_k^2 = (-1)^k$

$证明:$

首先要知道 $二阶行列式$ 的相关内容如下.

$二阶行列式$: $det egin{pmatrix} a b \ c d end{pmatrix} =ad-bc$

再看斐波那契数列的转移矩阵如下,

$egin{bmatrix} 1 1 \ 1 0 end{bmatrix}^k = egin{bmatrix} F_{k+1} F_k \ F_k F_{k-1} end{bmatrix}$

矩阵相等, 行列式也相等,

$herefore (-1)^k \ = F_{k+1}F_{k-1} - F_k^2\ = F_{k-1}^2+F_{k-1}F_k-F_k^2$

$得证$ .

所以在 $mod F_k$ 意义下, $(-1)^k=F_{k-1}^2$ .

---

再看原式: $F_i = F_{k-1}^{lfloor frac{i}{k} floor}F_{i\%k}$

设 $x= lfloor frac{i}{k} floor$, $y=i\%k$,

则 $F_i = F_{k-1}^xF_{y}=egin{cases} x&1 == 0, (-1)^{frac{x}{2}k} F_y\ x&1 == 1, (-1)^{(frac{x}{2}+1)k} F_{y-k} = (-1)^{(frac{x}{2}+1)k+k-y-1} F_{k-y} end{cases}$

---

其中 $F_{y-k}$ 可能为负数, 这里又要引入

$斐波那契的负系数项:F_{-i} = (-1)^{i-1}F_i$ .

然后就可以 $AC$ 辣 $!$

总结一下, 该题涉及的知识点有 $↓$

• $F_i = F_kF_{i-k+1}+F_{k-1}F_{i-k}$
• $F_{k-1}^2+F_{k-1}F_{k}-F_k^2 = (-1)^k$
• $F_{-i} = (-1)^{i-1}F_i$

---

$color{red}{实现部分}$

#include<bits/stdc++.h>
#define reg register
typedef long long ll;

const int mod = 1e9 + 7;

ll N;
ll K;

struct Matrix{ int C[4][4]; Matrix(){ memset(C, 0, sizeof C); } };

Matrix modify(const Matrix &a, const Matrix &b){
        Matrix s;
        for(reg int i = 1; i <= 2; i ++)
                for(reg int j = 1; j <= 2; j ++)
                        for(reg int k = 1; k <= 2; k ++){
                                int &t = s.C[i][j];
                                t = (1ll*t + (1ll*a.C[i][k]*b.C[k][j]%mod)) % mod;
                        }
        return s;
}

Matrix ma_Ksm(Matrix a, ll b){
        Matrix s;
        for(reg int i = 1; i <= 2; i ++) s.C[i][i] = 1;
        while(b){
                if(b & 1) s = modify(s, a);
                a = modify(a, a); b >>= 1;
        }
        return s;
}

ll get(ll k){
        Matrix res, I;
        res.C[1][1] = 1;
        I.C[1][1] = I.C[1][2] = I.C[2][1] = 1;
        I = ma_Ksm(I, k);
        res = modify(res, I);
        return res.C[1][2];
}

void Work(){
        scanf("%lld%lld", &N, &K);
        ll x = N/K, y = N%K;
        if(x & 1){
                x = (x+1)/2, y = K-y-1;
                x = (K & 1) * x;
                ll Ans = ((x+y&1)?-1:1) * get(y + 1);
                if(Ans < 0) Ans = (Ans + get(K) + mod) % mod;
                printf("%lld
", Ans);
        }else{
                x >>= 1;
                if(!(K&1)) x = 0;
                ll Ans = ((x&1)?-1:1) * get(y);
                if(Ans < 0) Ans = (Ans + get(K) + mod) % mod;
                printf("%lld
", Ans);
        }
}

int main(){ 
        freopen("fib.in", "r", stdin);
        freopen("fib.out", "w", stdout);
        int T; scanf("%d", &T);
        while(T --) Work();
        return 0;
}