F i b (K)$

Fib(N)表示斐波那契数列的第N项（ $F (0) = 0, F (1) = 1$ ），给出N和K，求 $F i b (N) m o d F i b (K)$ 。由于结果太大，输出 $M o d <mtext> </mtext> 1000000007$ 的结果。

$<mstyle mathcolor="red"> 正解部分 </mstyle>$

首先要知道

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

在 $m o d <mtext> </mtext> F_{k}$ 意义下继续化简 $↓$

$F_{i} = F_{k - 1} F_{i - k} = F_{k - 1} (F_{k} F_{i - 2 k + 1} + F_{k - 1} F_{i - k - k}) = F_{k - 1}^{2} F_{i - 2 k} <mtext> </mtext>&NegativeThinSpace; \dots = F_{k - 1}^{⌊ \frac{i}{k} ⌋} F_{i % k}$

再要知道

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

$证明 :$

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

$二阶行列式$ : $d e t (\begin{matrix} <mstyle displaystyle="false" scriptlevel="0"> a <mtext> </mtext> b </mstyle> \\ <mstyle displaystyle="false" scriptlevel="0"> c <mtext> </mtext> d </mstyle> \end{matrix}) = a d - b c$

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

${[\begin{matrix} <mstyle displaystyle="false" scriptlevel="0"> 1 <mtext> </mtext> 1 </mstyle> \\ <mstyle displaystyle="false" scriptlevel="0"> 1 <mtext> </mtext> 0 </mstyle> \end{matrix}]}^{k} = [\begin{matrix} <mstyle displaystyle="false" scriptlevel="0"> F_{k + 1} <mtext> </mtext> F_{k} </mstyle> \\ <mstyle displaystyle="false" scriptlevel="0"> F_{k} <mtext> </mtext> F_{k - 1} </mstyle> \end{matrix}]$

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

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

$得证$ .

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

再看原式: $F_{i} = F_{k - 1}^{⌊ \frac{i}{k} ⌋} F_{i % k}$

设 $x = ⌊ \frac{i}{k} ⌋$ , $y = i % k$ ,

则 $F_{i} = F_{k - 1}^{x} F_{y} = {\begin{matrix} <mstyle displaystyle="false" scriptlevel="0"> x & 1 = = 0, <mtext> </mtext> (- 1)^{\frac{x}{2} k} F_{y} </mstyle> \\ <mstyle displaystyle="false" scriptlevel="0"> x & 1 = = 1, <mtext> </mtext> (- 1)^{(\frac{x}{2} + 1) k} F_{y - k} = (- 1)^{(\frac{x}{2} + 1) k + k - y - 1} F_{k - y} </mstyle> \end{matrix}$

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

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

然后就可以 $A C$ 辣 $!$

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

$F_{i} = F_{k} F_{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}$

$<mstyle mathcolor="red"> 实现部分 </mstyle>$

#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\n", 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\n", Ans);
        }
}

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

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

F i b ( N ) <mtext> </mtext> m o d <mtext> </mtext> F i b ( K ) Fib(N)\ mod\ Fib(K) Fib(N) mod Fib(K)

<mstyle mathcolor="red"> 正 解 部 分 </mstyle> \color{red}{正解部分} 正解部分

F i = F k F i − k + 1 + F k − 1 F i − k F_i = F_kF_{i-k+1}+F_{k-1}F_{i-k} Fi​=Fk​Fi−k+1​+Fk−1​Fi−k​,

F k − 1 2 + F k − 1 F k − F k 2 = ( − 1 ) k F_{k-1}^2+F_{k-1}F_{k}-F_k^2 = (-1)^k Fk−12​+Fk−1​Fk​−Fk2​=(−1)k

证 明 : 证明: 证明:

得 证 得证 得证 .