AcWing 1303. 斐波那契前 n 项和
原题链接
中等
作者:
Snrise
,
2024-04-08 19:42:43
,
所有人可见
,
阅读 2
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#define endl '\n'
#define int long long
using namespace std;
const int N = 3;
int n, MOD;
int a[N][N] = {1, 0, 0, 1, 1, 1, 0, 1, 0};
int f[N][N] = {0, 1, 0};
void mul(int c[N][N], int a[N][N], int b[N][N])
{
int t[N][N] = {0};
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
for (int k = 0; k < N; k++)
{
t[i][j] = (t[i][j] + a[i][k] * b[k][j]) % MOD;
}
}
}
memcpy(c, t, sizeof(t));
}
signed main(void)
{
std::ios::sync_with_stdio(false);
cin >> n >> MOD;
while (n)
{
if (n & 1)
{
mul(f, f, a);
}
mul(a, a, a);
n >>= 1;
}
cout << f[0][0] << endl;
return 0;
}
矩阵快速幂吗
对的