简单的找规律可得长度为 n 的方案数 = 长度为 n−1 的方案数 + 长度为 n−2 发现就是魔改的Fibonacci数列：
1,2,3,5,8,11......
但是 O(n) 递推只能拿70分，考虑矩阵快速幂优化。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| #include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const long long mod = 100000007;
ifstream fin("siege.in");
ofstream fout("siege.out");
long long n, res;
struct Matrix {
vector<vector<long long> > arr;
int row, col;
Matrix() = default;
inline Matrix(int r, int c) {
arr.resize(r + 1);
for(auto &vec : arr) vec.resize(c + 1);
row = r, col = c;
}
inline void resize(int r, int c) {
arr.resize(r + 1);
for(auto &vec : arr) vec.resize(c + 1);
row = r, col = c;
}
inline static Matrix unit(int squ) {
Matrix res(squ, squ);
for(int i = 1; i <= squ; i++) res.arr[i][i] = 1;
return res;
}
inline Matrix operator*(const Matrix m) const {
Matrix res(row, m.col);
for(int i = 1; i <= row; i++)
for(int j = 1; j <= m.col; j++)
for(int k = 1; k <= col; k++)
res.arr[i][j] += (arr[i][k] * m.arr[k][j]) % mod, res.arr[i][j] %= mod;
return res;
}
inline Matrix operator^(long long power) {
Matrix res = unit(row);
do {
if (power & 1) res = res * *this;
*this = *this * *this;
power >>= 1;
} while(power);
return res;
}
};
Matrix a, b, c;
int fib() {
if(n == 1) return 1;
if(n == 2) return 2;
a.resize(1, 2);
b.resize(2, 2);
a.arr[1][1] = 2, a.arr[1][2] = 1;
b.arr[1][1] = b.arr[1][2] = b.arr[2][1] = 1;
c = b ^ (n - 1);
c = a * c;
return c.arr[1][1];
}
int main() {
fin >> n;
fout << fib() << endl;
return 0;
}
|