1 条题解
-
1
极致的时间复杂度要求
你打开了这道题;你发现是经典的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周期。它也是我们对什么数取模的来源。下方是链接。
那么根据上面这篇论文,我们的步骤如下:
- 对 𝑃进行质因数分解,时间复杂度 O(根号P);
- 对于 P 的每个质因数分解Pi ki,求出对应的周期长 𝜋(𝑝𝑖𝑘𝑖);
- 求出每个周期的最小公倍数,作为 𝜋(𝑃) 的值;
- 把读入的 𝑛模以 𝜋(𝑃),然后矩阵快速幂解决。
不多说了,贴一下代码。
#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
- 上传者