LOJ #10222 佳佳的Fibonacci

很久没写矩阵乘优化递推的题了，写的很坎坷。

首先我们要求的就是(sum i F_i).然后这玩意递推不能。GMK传授我把i+1康康。

((i+1)F_{i+1}=(i + 1)(F_i + F_{i -1})=iF_i + F_i + (i - 1)F_{i -1} + 2F_{i - 1})。这玩意就可以用矩阵啦。

写这题犯了一堆SB错误。。。

1.重载乘号没return（？

2.写转移矩阵的时候把那个系数2写成1调半天。。。

3.我的快速幂从n-2开始算的，得特判1。。。鲁棒性不足

#include <bits/stdc++.h>
#define ll long long

ll n, p;

struct Matrix {
    ll a[10][10];
    Matrix() { memset(a, 0, sizeof(a)); }
    void QAQ() {
        a[1][1] = a[2][1] = a[3][1] = a[4][2] = a[1][3] = a[2][2] = a[2][4] = a[1][5] = a[5][5] = 1,
        a[4][1] = 2;
    }
    friend Matrix operator*(Matrix x, Matrix y) {
        Matrix z;
        for (int k = 1; k <= 5; k++)
            for (int i = 1; i <= 5; i++)
                for (int j = 1; j <= 5; j++) z.a[i][j] = (z.a[i][j] + x.a[i][k] * y.a[k][j]) % p;
        return z;
    }
};

Matrix qpow(Matrix x, int b) {
    Matrix ret = x;
    for (; b; b >>= 1, x = x * x)
        if (b & 1)
            ret = ret * x;
    return ret;
}

signed main() {
    scanf("%lld%lld", &n, &p);
    if (n == 1) {
        puts("1");
        return 0;
    }
    Matrix tmp;
    tmp.QAQ();
    Matrix ans;
    ans.a[1][1] = 2, ans.a[1][2] = 1, ans.a[1][3] = ans.a[1][4] = 1, ans.a[1][5] = 1;
    tmp = qpow(tmp, n - 2);
    ans = ans * tmp;
    printf("%lld
", ans.a[1][5]);
    return 0;
}