矩阵快速幂加速递推

来自本人luogu的blog搬运

#include <iostream>
#define ll long long
using namespace std;
const int maxn = 100, maxm = 100;
int i, j, mod;
struct matrix
{
  int n, m;
  ll s[maxn][maxm];
  matrix()
  {
    clean();
  }
  void clean()
  {
    n = maxn, m = maxm;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        s[i][j] = 0;
  }                                  
} A, F0;                             //F0为初始矩阵，A为构造出的矩阵
long long ss[maxn];                  
matrix operator*(matrix a, matrix b) //重载*运算符
{
  matrix c;
  if (a.m != b.n)
    return c;
  c.n = a.n, c.m = a.m;
  for (int j = 0; j < c.m; j++)
  {
    for (int i = 0; i < c.n; i++)
      ss[i] = b.s[i][j];
    for (int i = 0; i < c.n; i++)
    {
      for (int k = 0; k < a.m; k++)
        c.s[i][j] += a.s[i][k] * ss[k];
      c.s[i][j] %= mod;
    }
  }
  return c;
}
matrix pow(matrix a, int b)
{
  matrix ans;
  ans.n = a.n, ans.m = a.m;
  for (int i = 0; i < a.n; i++)
    for (int j = 0; j < a.m; j++)
      ans.s[i][j] = (i == j); //构造单位矩阵
  while (b)
  {
    if (b & 1)
      ans = ans * a;
    a = a * a;
    b = b >> 1;
  }
  return ans;
}
int n, k = 2; //k为初始值个数，根据需要取
int main()
{
  for (i = 0; i < k; i++)
    cin >> A.s[0][i];
  for (i = 0; i < k; i++)
    A.s[i][i - 1] = 1;
  for (i = 0; i < k; i++)
    cin >> F0.s[k - i - 1][0];
  cin >> n >> mod;
  A.m = A.n = k, F0.m = 1, F0.n = k;
  if (n < k)
  {
    cout << F0.s[k - n - 1][0] << endl;
    return 0;
  }
  cout << (pow(A, n - k) * F0).s[0][0]; 
}