1 条题解

  • 1
    @ 2024-6-7 0:22:13

    极致的时间复杂度要求

    你打开了这道题;你发现是经典的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不过分吧。。

    • 1

    信息

    ID
    165
    时间
    500~5000ms
    内存
    128MiB
    难度
    7
    标签
    递交数
    44
    已通过
    1
    上传者