感觉一天时间过得挺快，而自己却没有什么收获。

1.之前恰好看了跟快速幂乘法一样的计算大数乘法模，防止溢出，感觉挺有用的，而且用的挺多的。

2.分析问题的能力还很差，遇到一个问题，无法正确的进行转化，怎么进行考虑，感觉自己这方面还很欠缺，这应该是通过大量做题，然后不断总结得出来的吧！毕竟题做的多了，遇到新题也就那几种套路。感觉也是挺对的，面试题的那些小套路在搞竞赛的人面前根本什么也不是，感觉这句话挺有道理的。

3. 这次做的这道题，最后就是转化为求第n个斐波那契数，而我根本没有推导出这个。然后，之前做过怎么快速求解，一个是根据递推公式，还想是f(n)可以通过f(n/2),f(n/2 + 1), f(n/2 - 1)这几个数导出来，我也懒得记，遇到的时候就拿前几个数推导一下，很简单的。另一个方法，就是转移矩阵，快速幂求解。这个方法算是通用的方法（套路），大多数题，搞出来递推公式，可能转移条件比较多，然后搞成转移矩阵的形式，给出初始值，然后求第n个，就是求矩阵的n次幂，然后就是快速幂乘法。这个方法很重要。

4. 忘了，这次还有一点非常重要，就是leetcode上面house robber 那题，思路倒不是挺难，但是感觉自己写的代码很丑，然后今天遇到类似的转化，就很麻烦。然后看题解，得出一种巧妙的方法。题目要求不能出现连续的1，因为是环形的，要求第一个和最后一个不能同时是1，这就增加的复杂性，你不能简单的一次递推，然后考虑这样，枚举第一个位置是0，然后从第二个位置开始，随意放，可以放还可以不放，最后的答案就是最后一个放和不放的总和，第二种情况是：第一个放，那么第二个不能放，然后从第三个开始，可以随意放，然后就转化成前面的那个问题，而且不用重复计算，最后的答案就是最后一个不能放的个数，最终把这两种情况加起来就是最后的答案。这样代码写出来，看起来也特别整齐。仔细想想，真的很巧妙！

下面贴一下我写的求斐波那契：

1 #include 
     
       2 using namespace std; 3 typedef long long ll; 4 const int maxn = 1e6 + 10; 5 const int mod = 1e9 + 7; 6 ll dp[maxn][2]; 7 ll n; 8 map
      
        ma; 9 ll work(ll x) {10     if(x == 0) return 1;11     if(x < 4) return x;12     if(ma.count(x)) return ma[x];13     ll res = 0;14     ll t = x / 2;15     if(x & 1) {16         res = work(t) * (work(t - 1) + work(t + 1)) % mod;17     } else {18         res = work(t) * work(t) % mod + work(t - 1) * work(t - 1) % mod;19     }20     return ma[x] = res;21 }22 void solve() {23     cin >> n;24     ll res = (work(n) + work(n - 2)) % mod;25     cout << res << endl;26 }27 int main() {28     solve();29     /* Enter your code here. Read input from STDIN. Print output to STDOUT */   30     return 0;31 }
      
     

1 #include
     
       2 #define pb push_back 3 #define FOR(i, n) for (int i = 0; i < (int)n; ++i) 4 #define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl 5 typedef long long ll; 6 using namespace std; 7 typedef pair
      
        pii; 8 const int maxn = 1e3 + 10; 9 const int mod = 1e9 + 7;10 struct mat {11     ll a[4];12     void init() {13         a[0] = a[3] = 1;14         a[1] = a[2] = 0;15     }16     mat mul(const mat &x) {17         mat res;18         res.a[0] = (a[0] * x.a[0] % mod + a[1] * x.a[2] % mod) % mod;19         res.a[1] = (a[0] * x.a[1] % mod + a[1] * x.a[3] % mod) % mod;20         res.a[2] = (a[2] * x.a[0] % mod + a[3] * x.a[2] % mod) % mod;21         res.a[3] = (a[2] * x.a[1] % mod + a[3] * x.a[3] % mod) % mod;22         return res;23     }24 };25 mat pow(mat a, ll b) {26     mat res;27     res.init();28     while(b) {29         if(b & 1) res = res.mul(a);30         a = a.mul(a);31         b >>= 1;32     }33     return res;34 }35 ll fb(ll n) {36     if(n == 0) return 1;37     if(n < 4) return n;38     mat t;39     t.a[0] = 0; t.a[1] = 1; t.a[2] = 1; t.a[3] = 1;40     t = pow(t, n);41     return t.a[3];42 }43 ll n;44 void solve() {45     while(cin >> n) {46 47         ll res = (fb(n) + fb(n - 2)) % mod;48         cout << res << endl;49     }50 }51 int main() {52     //freopen("test.in", "r", stdin);53     //freopen("test.out", "w", stdout);54     solve();55     return 0;56 }