题目描述
大家都知道 Fibonacci 数列吧,f1=1,f2=1,f3=2,f4=3,…,fn=fn−1+fn−2
。
现在问题很简单,输入 n
和 m
,求 fn
的前 n
项和 Snmodm
。
输入格式
共一行,包含两个整数 n
和 m
。
输出格式
输出前 n
项和 Snmodm
的值。
数据范围
1≤n≤2000000000
,
1≤m≤1000000010
样例
5 1000
算法
结论:Sn = Sn-1 + Sn-2 + 1
证明:
Sn = Sn-1 + fn
Sn-2 = fn-2 + fn-3 + fn-4 + fn-5 +…+f0
fn = fn-1 + fn-2
= (fn-2 + fn-3) + fn-2
= (fn-2 + fn-3) + (fn-3 + fn-4)
= (fn-2 + fn-3 + fn-4) + fn-3
= (fn-2 + fn-3 + fn-4) + (fn-4 + fn-5)
= (fn-2 + fn-3 + fn-4 + fn-5) + fn-4
…
= (fn-2 +…+f0) + f1
= Sn-2 + f1
= Sn-2 + 1
所以:Sn = Sn-1 + Sn-2 + 1
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long int LL;
void mul(LL A[][3], LL F[][3], LL m)
{
LL C[3][3] = {0};
for(int i = 0; i < 3; i ++)
for(int j = 0; j < 3; j ++)
for(int k = 0; k < 3; k ++)
C[i][j] = (C[i][j] + A[i][k] * F[k][j]) % m;
memcpy(A, C, sizeof C);
}
LL fib(LL n, LL m)
{
LL A[3][3] = {0, 1, 1, 0, 0, 0, 0, 0, 0}; //[an, an+1, 1] [0, 1, 0] [an+1, an + an+1 + 1, 1]
LL F[3][3] = {0, 1, 0, 1, 1, 0, 0, 1, 1}; //[0, 0, 0] * [1, 1, 0] = [0 , 0 , 0]
while(n) //[0, 0, 0] [0, 1, 1] [0 , 0 , 0]
{
if(n & 1)mul(A, F, m);
mul(F, F, m);
n >>= 1;
}
return A[0][0];
}
int main()
{
LL n, m;
scanf("%lld%lld", &n, &m);
printf("%lld", fib(n, m));
return 0;
}