题目描述
大家都知道 Fibonacci 数列吧,f1=1,f2=1,f3=2,f4=3,…,fn=fn−1+fn−2。
现在问题很简单,输入 n 和 m,求 fn 的前 n 项和 Sn mod m。
样例
输入样例:
5 1000
输出样例:
12
算法1
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 3;
int n, m;
void mul(int c[], int a[], int b[][N])
{
int temp[N] = {0};
for (int i = 0; i < N; i ++ )
for (int j = 0; j < N; j ++ )
temp[i] = (temp[i] + (LL)a[j] * b[j][i]) % m;
memcpy(c, temp, sizeof temp);
}
void mul(int c[][N], int a[][N], int b[][N])
{
int temp[N][N] = {0};
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] + (LL)a[i][k] * b[k][j]) % m;
memcpy(c, temp, sizeof temp);
}
int main()
{
cin >> n >> m;
int f1[N] = {1, 1, 1};
int a[N][N] = {
{0, 1, 0},
{1, 1, 1},
{0, 0, 1}
};
n -- ;
while (n)
{
if (n & 1) mul(f1, f1, a); // f1 = f1 * a
mul(a, a, a); // a = a * a
n >>= 1;
}
cout << f1[2] << endl;
return 0;
}