大家都知道 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
输出样例：
12
矩阵快速幂板子题。设前n项和为\(S_n\)，有\(S_n - S_{n - 1} = f_n = f_{n - 1} + f_{n - 2} = S_{n - 1} - S_{n - 2} + S_{n - 2} - S_{n - 3}\)，得到\(S_n = 2\times S_{n - 1} - S_{n - 3}\)，显然转移矩阵为：
2 0 -1
1 0 0
0 1 0
搞一搞就行了
注意转移矩阵有减法，在进行矩阵乘法的时候注意多加几个mod防爆！！！
#include <bits/stdc++.h>
#define LL long long
using namespace std;
#define int long long
#define N 3
struct Mat
{
LL m[101][101];
void print() {
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= N; j++) {
cout << m[i][j] << " ";
}
cout << endl;
}
}
};//存储结构体
Mat a,e; //a是输入的矩阵，e是输出的矩阵
Mat Mul(Mat x,Mat y, long long mod)
{
Mat c;
for(int i=1;i<=N;++i){
for(int j=1;j<=N;++j){
c.m[i][j] = 0;
}
}
for(int i=1;i<=N;++i){
for(int j=1;j<=N;++j){
for(int k=1;k<=N;++k){
c.m[i][j] = (c.m[i][j]%mod + x.m[i][k]%mod*y.m[k][j]%mod + mod + mod) % mod;//注意有减法！！得多加mod 要不然就爆了
}
}
}
return c;
}
Mat pow(Mat x,LL y, long long mod)//矩阵快速幂
{
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= N; j++) {
e.m[i][j] = 0;
}
}
for(int i = 1; i <= N; i++) {
e.m[i][i] = 1;
}
Mat ans = e;
while(y){
if(y&1) ans = Mul(ans,x,mod);
x = Mul(x,x,mod);
y>>=1;
}
return ans;
}
long long n, m;
signed main() {
cin >> n >> m;
Mat base;
for(int i = 1; i <= 3; i++) {
for(int j = 1; j <= 3; j++) {
base.m[i][j] = 0;
}
}
base.m[1][1] = 2, base.m[1][3] = -1, base.m[2][1] = 1, base.m[3][2] = 1;
//base.print();
Mat S;
for(int i = 1; i <= 3; i++) {
for(int j = 1; j <= 3; j++) {
S.m[i][j] = 0;
}
}
S.m[1][1] = 4, S.m[2][1] = 2, S.m[3][1] = 1;
if(n == 1) cout << 1;
else if(n == 2) cout << 2;
else if(n == 3) cout << 4;
else {
Mat tmp = pow(base, n - 3, m);
Mat ans = Mul(tmp, S, m);
cout << ans.m[1][1];
}
return 0;
}