极致的时间复杂度要求

你打开了这道题；你发现是经典的fibonacci 数列；你熟练地写出矩阵快速幂并提交； 会成功吗？ 如成。 前两个subtask很快的跳出来绿色的accepted，你觉得稳了；然后猛一转头，诶？？？不对劲啊，subtask3怎么过了5秒还没跳出来？ 哦，终于跳出来了。定睛一看，颜色不大对啊，寄，第一个点就Time Exceeded！ 然后后面直接一片灰茫茫的cancelled，就如同你此刻的心情。 以上就是我第一遍做这个题的过程。

但我没有意外，因为我是TLE本体

附上最初的暴力迭代以及矩阵快速幂的代码。 【暴力迭代】

#include <iostream>
 using namespace std;
 typedef long long ll;

 ll fibMod(ll n, ll p) {
    if (n == 0) return 0;
    if (n == 1 || n == 2) return 1;

    ll a = 1, b = 1, c;
     for (ll i = 3; i <= n; ++i) {
        c = (a + b) % p;
        a = b;
         b = c;
     }
    return b;
 }

 int main() {
     int T;
     cin >> T;
    while (T--) {
        ll n, p;
         cin >> n >> p;
      cout << fibMod(n, p) << endl;
    }
     return 0;
 }
 //以上直接循环迭代计算，能算斐波那契数列的值，但是会TLE。

【矩阵快速幂】

//矩阵快速幂
 #include <iostream>
 #include <vector>
 using namespace std;

 typedef long long ll;

 // Matrix multiplication without modulo
 vector<vector<ll>> matMulNoMod(const vector<vector<ll>>& A, const vector<vector<ll>>& B) {
     int n = A.size();
     vector<vector<ll>> C(n, vector<ll>(n, 0));
     for (int i = 0; i < n; ++i) {
         for (int j = 0; j < n; ++j) {
             for (int k = 0; k < n; ++k) {
                 C[i][j] += A[i][k] * B[k][j];
             }
         }
     }
     return C;
 }

 // Matrix exponentiation without modulo
 vector<vector<ll>> matPowNoMod(vector<vector<ll>> A, ll exp) {
     int n = A.size();
     vector<vector<ll>> res(n, vector<ll>(n, 0));
     for (int i = 0; i < n; ++i) {
         res[i][i] = 1;  // Identity matrix
     }

     while (exp) {
         if (exp % 2 == 1) {
             res = matMulNoMod(res, A);
         }
         A = matMulNoMod(A, A);
        exp /= 2;
    }
    return res;
}

// Function to find nth Fibonacci number
ll fibNoMod(ll n) {
    if (n == 0) return 0;
    if (n == 1 || n == 2) return 1;

    vector<vector<ll>> F = {{1, 1}, {1, 0}};
    F = matPowNoMod(F, n - 1);
    return F[0][0];  // The (0,0) element gives us F(n)
}

// Function to find nth Fibonacci number modulo p using matrix exponentiation
ll fibModMatrix(ll n, ll p) {
    ll fib_n = fibNoMod(n);
    return fib_n % p;
}

// Linear iteration to find nth Fibonacci number modulo p
ll fibModLinear(ll n, ll p) {
    if (n == 0) return 0;
    if (n == 1 || n == 2) return 1;

    ll a = 1, b = 1, c;
    for (ll i = 3; i <= n; ++i) {
        c = (a + b);
        a = b;
        b = c;
    }
    return b % p;
}

int main() {
    int T;
     cin >> T;
     while (T--) {
         ll n, p;
         cin >> n >> p;
         if (n <= 10000000000000) {
             // For small values of n, use linear iteration
             cout << fibModLinear(n, p) << endl;
         } else {
             // For large values of n, use matrix exponentiation
             cout << fibModMatrix(n, p) << endl;
         }
     }
     return 0;
 }

显然可以看到我多次想要偷鸡 根据题中所给修改n的范围。我最初甚至以为是我误把迭代用在了很大的数上。结果后来一想，矩阵快速幂本身也会TLE,究其原因就是这题的数据集太过逆天，竟然达到了10^30000000,我们知道计算机的计算速度也就是每秒一千万次，然后矩阵快速幂虽然已经很牛逼了，是O（logn）但是算出来还是不够。 所以，我们需要更牛逼的降低时间复杂度。

因为这道题的TLE来源是数据集太过逆天太大了，所以我们自然的想到，可以先对n模以某个数，然后再矩阵快速幂.

这可能需要一些数论知识，比如二次剩余，原根，还有最重要的，解决这道题的最终一击----pisano周期。它也是我们对什么数取模的来源。下方是链接。

Pisano 周期 - 知乎 (zhihu.com)

那么根据上面这篇论文，我们的步骤如下：

1. 对 𝑃进行质因数分解，时间复杂度 O(根号P）；
2. 对于 P 的每个质因数分解Pi ki​，求出对应的周期长 𝜋(𝑝𝑖𝑘𝑖)；
3. 求出每个周期的最小公倍数，作为 𝜋(𝑃) 的值；
4. 把读入的 𝑛模以 𝜋(𝑃)，然后矩阵快速幂解决。

不多说了，贴一下代码。

#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;

ll FastPow(ll a, ll b, ll mod){
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % mod;
        b >>= 1, a = a * a % mod;
    }
    return res;
}

ll FastPowNoMod(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1) res = res * a;
        b >>= 1, a = a * a;
    }
    return res;
}

const int Mx = 3e7 + 10;
int Fac[30], Tim[30], tot;
char N[Mx];

void Divide(int p){ // 分解质因数
    for(int i = 2; i * i <= p; ++i) if(p % i == 0){
        Fac[++tot] = i;
        while(p % i == 0) p /= i, ++Tim[tot];
    }
    if(p != 1) Fac[++tot] = p, Tim[tot] = 1;
}

ll PrimeLoop(ll p){ // 求 pi(p)
    if(p == 2) return 3;
    if(p == 5) return 20;
    if(FastPow(5, (p - 1) >> 1, p) == 1) return p - 1;
    return 2 * p + 2;
}

ll PrimePow(int id){ return FastPowNoMod(Fac[id], Tim[id] - 1) * PrimeLoop(Fac[id]);} // 求 pi(p^k)

ll Gcd(ll a, ll b){ return b == 0 ? a : Gcd(b, a % b);}

ll GetLoop(){ // 求 pi(P)
    ll res = PrimePow(1), temp;
    for(int i = 2; i <= tot; ++i) temp = PrimePow(i), res = res / Gcd(res, temp) * temp;
    return res;
}

int P;

struct Matrix{
    ll val[3][3];
    Matrix operator * (const Matrix& a) const {
        Matrix Res = (*this);
        for(int i = 1; i <= 2; ++i) for(int j = 1; j <= 2; ++j)
            Res.val[i][j] = (val[i][1] * a.val[1][j] % P + val[i][2] * a.val[2][j] % P) % P;
        return Res;
    }
    Matrix operator *= (const Matrix& a) { return (*this) = a * (*this);}
    Matrix operator ^ (ll k) const {
        Matrix Res, Temp = (*this);
        Res.val[1][1] = Res.val[2][2] = 1, Res.val[1][2] = Res.val[2][1] = 0;
        while(k){
            if(k & 1) Res *= Temp;
            k >>= 1, Temp *= Temp;
        }
        return Res;
    }
} Fibo, Cell;

void Solve(ll n,int P){
    if(n == 0){
        printf("0");
        return;
    }
	Fibo.val[1][1] = 0, Fibo.val[2][1] = Fibo.val[1][2] = Fibo.val[2][2] = 1;
	Cell.val[1][1] = 1, Cell.val[1][2] = 1;
    Matrix Res = Cell * (Fibo ^ (n - 1));
    printf("%lld", Res.val[1][1] % P);
}

int main(){
    int T;
    scanf("%d", &T);
    while(T--)
    {
        int P;
        scanf(" %s %d", N, &P);
        if (P == 1)
        {
            printf("0");
    }
    Divide(P);
    ll Loop = GetLoop(), n = 0;
    int Len = strlen(N);
    for(int i = 0; i < Len; ++i) n = (n * 10 + (N[i] ^ 48)) % Loop;
    Solve(n,P); 
    }
    return 0;
}

在借鉴了无数资料（包括洛谷题解）之后，终于在看到这道题两天之后的某个凌晨。想出来。

再吐槽一下，这个题难度只有7是否有些低了。。它绝对有黑题难度了吧，给个10不过分吧。。