Description:

佳佳对数学，尤其对数列十分感兴趣。

在研究完 Fibonacci 数列后，他创造出许多稀奇古怪的数列。

例如用 S(n) 表示 Fibonacci 前 n 项和 modm 的值，即 S(n)=(F1+F2+…+Fn)modm，其中 F1=F2=1,Fi=Fi−1+Fi−2。

可这对佳佳来说还是小菜一碟。

终于，她找到了一个自己解决不了的问题。

用 T(n)=(F1+2F2+3F3+…+nFn)modm 表示 Fibonacci 数列前 n 项变形后的和 modm 的值。

现在佳佳告诉你了一个 n 和 m，请求出 T(n) 的值。

Solution:

假设
$$P_n = \sum_{k = 0}^{n} k F_{k + 1}$$

$$P_n + (n + 1)F_{n + 2}= \sum_{k = 0}^{n}(k + 1)F_{k + 2 } $$

$$P_n + (n + 1)F_{n + 2} = \sum_{k = 0}^{n}(k + 1) (F_{k + 1} + F_k) $$

$$Pn + (n + 1)F_{n + 2} = P_n + \sum_{k = 0}^{n} k F_k +\sum_{k = 0}^{n}F_{k + 1} + \sum_{k = 0}^{n} F_k $$

等式两边同时约去$\sum_{k = 0}^{n}kF_k$,再化简一下，可以得到

$$\sum_{k = 0}^{n} k F_k =nF_{n + 1} + (n + 1)F_n - 2 \sum_{k = 0}^{n}F_k $$

可以用矩阵乘法求出$\sum_{k = 0}^{n}F_k$

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

typedef long long LL;
const int N = 3;
LL f[N][N];
int n, m;

void mul(LL c[][N], LL a[][N], LL b[][N])
{
    LL tmp[N][N] = {0};
    for(int i = 0; i < N; i ++)
        for(int j = 0; j < N; j ++)
            for(int k = 0; k < N; k ++)
                tmp[i][j] = (tmp[i][j] + (LL)a[i][k] * b[k][j]) % m;
    memcpy(c, tmp, sizeof(tmp));
}

void print(int a[][N])
{
    for(int i = 0; i < N; i ++) {
        for(int j = 0; j < N; j ++) {
            printf("%d ", a[i][j]);
        }
        puts("");
    }
    puts("");
}

void quick_pow()
{
    LL a[N][N] = {
        {0, 1, 0},
        {1, 1, 1},
        {0, 0, 1}
    };
    f[0][0] = 0, f[0][1] = 1, f[0][2] = 0;
    for(int b = n; b; b >>= 1) {
        if( b & 1) mul(f, f, a);
        mul(a, a, a);
//      print(a);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
//  m = 1000;
    quick_pow();
    printf("%lld\n", ((n * f[0][1] + ( n + 1) * f[0][0] - 2 * f[0][2] ) + m ) % m);
}