从0开始的矩阵乘法

因为sum[i] = sum[i - 1] + i * f[i]
我们构建F[i] = [f[i], f[i + 1], i * f[i], (i + 1) * f[i + 1], sum[i]]
则递推的 F[i + 1] = [f[i + 1], f[i + 2], (i + 1) * f[i + 1], (i + 2) * f[i + 2], sum[i + 1]]
则此时的转置矩阵

    A = {
            {0, 1, 0, 2, 0},
            {1, 1, 0, 1, 0},
            {0, 0, 0, 1, 0},
            {0, 0, 1, 1, 1},
            {0, 0, 0, 0, 1},
        };

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include <unordered_map>
using namespace std;

#define _ 0
#define PII pair<int, int>
#define int long long 
#define endl '\n'
const int N = 5;
const int INF = 2147483647;
const int mod = 1e9 + 7;
const  double eps = 1e-8;
const int pi = 3.1415926;

int n, m;

void mul(int c[][N], int a[][N], int b[][N])
{
   static int temp[N][N];
   memset(temp, 0, sizeof temp);
    for(int i = 0; i < N; i ++)
       for(int j = 0; j < N; j ++)
           for(int k = 0; k < N; k ++)
              temp[i][j] = (temp[i][j] + a[i][k] * b[k][j]) % m;

    memcpy(c, temp, sizeof temp);          
}

void solve()
{
    cin >> n >> m;

    int f1[N][N] = {1, 1, 1, 2, 1};// f[i]   f[i + 1]   i * f[i]   (i + 1) * f[i + 1]   sum[i]
    int a[N][N] ={
        {0, 1, 0, 2, 0},
        {1, 1, 0, 1, 0},
        {0, 0, 0, 1, 0},
        {0, 0, 1, 1, 1},
        {0, 0, 0, 0, 1},
    };

    n --;
    while(n)
    {
        if(n & 1) mul(f1, f1, a); //res = res * a
        mul(a, a, a); // a = a * a
        n >>= 1;
    }

    cout << f1[0][4] << endl;
}

signed main()
{
    ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T = 1;
    //cin >> T;
     while(T --)
     solve();
  //cout << fixed <<setprecision(0) <<endl;
    return ~~(0 ^ _ ^ 0);
}
/*
*
*　　┏┓　　　┏┓+ +
*　┏┛┻━━━┛┻┓ + +
*　┃　　　　　　　┃
*　┃　　　━　　　┃ ++ + + +
*  ████━████+
*  ◥██◤　◥██◤ +
*　┃　　　┻　　　┃
*　┃　　　　　　　┃ + +
*　┗━┓　　　┏━┛
*　　　┃　　　┃ + + + +Code is far away from 　
*　　　┃　　　┃ + bug with the animal protecting
*　　　┃　 　 ┗━━━┓ 神兽保佑,代码无bug　
*　　　┃ 　　　　　　 ┣┓
*　　  ┃ 　　　　　 　┏┛
*　    ┗┓┓┏━┳┓┏┛ + + + +
*　　　　┃┫┫　┃┫┫
*　　　　┗┻┛　┗┻┛+ + + +
*/