C++代码O(logn)实现:有一个数字n(n<=1e9),设f(n)为当n<=20时,f(n)=n,否则f(n)=f(n-10)+f(n-20),请你求出最后f(n)的值,输入样例 23 输出样例 16
时间: 2023-09-23 19:03:40 浏览: 34
下面是一份时间复杂度为 O(logn) 的 C++ 代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
typedef vector<vector<int>> matrix;
const int MOD = 1e9 + 7;
matrix operator * (const matrix& a, const matrix& b) {
int n = a.size(), m = b[0].size(), k = a[0].size();
matrix c(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int t = 0; t < k; t++) {
c[i][j] += (long long)a[i][t] * b[t][j] % MOD;
c[i][j] %= MOD;
}
}
}
return c;
}
matrix pow(matrix a, int n) {
int m = a.size();
matrix res(m, vector<int>(m));
for (int i = 0; i < m; i++) {
res[i][i] = 1;
}
while (n) {
if (n & 1) {
res = res * a;
}
a = a * a;
n >>= 1;
}
return res;
}
int main() {
int n;
cin >> n;
if (n <= 20) {
cout << n << endl;
} else {
matrix a = {{1, 1}, {1, 0}};
matrix b = {{11}, {1}};
matrix c = pow(a, (n - 20) / 10);
matrix res = c * b;
cout << res[0][0] << endl;
}
return 0;
}
```
该代码利用了矩阵快速幂来求解,时间复杂度为 O(logn)。其中,矩阵 a 和 b 分别表示:
```
| f(n-10) |
| f(n-20) |
```
```
| 11 |
| 1 |
```
矩阵 c 表示矩阵 a 的 (n-20)/10 次方,res 表示最终的结果,即 f(n)。