1303. 斐波那契前 n 项和

2023-11-04 09:35:16

题目链接

1303. 斐波那契前 n 项和

输入 \(n\) 和 \(m\)，求 Fibonacci数列的前 \(n\) 项和 \(S_n\bmod m\)。

输入格式

共一行，包含两个整数 \(n\) 和 \(m\)。

输出格式

输出前 \(n\) 项和 \(S_n\bmod m\) 的值。

数据范围

\(1≤n≤2000000000,\)
\(1≤m≤1000000010\)

输入样例：

5 1000

输出样例：

解题思路

矩阵乘法，快速幂

构造一个函数 \(f_n=[F_n,F_{n+1},s_n]\)，寻找 \(f_n\) 和 \(f_{n+1}\) 之间的关系，即 \(f_{n+1}=f_n\times A\)，可得 \( A= \begin{bmatrix} 0 &1 &0 \\ 1 &1 &1 \\ 0 &0 &1 \end{bmatrix} \)
则有 \(f_n=f_1\times A^{n-1}\)，可用快速幂配合矩阵乘法快速求解 \(f_n\)

时间复杂度：\(O(3^3\times logn)\)

推式子

有 \(F_{n+2}=F_{n+1}+F_{n}\)，即 \(F_n=F_{n+2}-F_{n+1}\)，则
\(\left\{\begin{array}{c}F_{1}=F_{3}-F_{2} \\ F_{2}=F_{4}-F_{3} \\ F_{3}=F_{5}-F_{4} \\ F_{4}=F_{6}-F_{5} \\ \vdots \\ F_{n}=F_{n+2}-F_{n+1}\end{array}\right.\)，得 \(s_n=F_{n+2}-F_2\)

时间复杂度：\(O(2^2\times logn)\)

快速倍增法
源自抽风巨佬

这里 \(f_n\) 为第 \(n\) 个 Fibonacci数列
结论： \(f_{n}=f_{k} f_{n-k+1}+f_{k-1} f_{n-k}(2\leq k \leq n)\)
证明：

\[\because f_{n}=f_{n-1}+f_{n-2}=f_{2} f_{n-2+1}+f_{1} f_{n-2} \]

\(\therefore\) 结论对于 \(k=2\) 成立
假设结论对于 \(k=i\) 成立
则有 \(f_{n}=f_{i} f_{n-i+1}+f_{i-1} f_{n-i}\)
\(\Rightarrow=f_{i}\left(f_{n-i}+f_{n-i-1}\right)+f_{i-1} f_{n-i}\)
\(\Rightarrow=f_{i} f_{n-i}+f_{i} f_{n-i-1}+f_{i-1} f_{n-i}\)
\(\Rightarrow=\left(f_{i}+f_{i-1}\right) f_{n-i}+f_{i} f_{n-i-1}\)
\(\Rightarrow=f_{i+1} f_{n-i}+f_{i} f_{n-i-1}\)
所以结论对于 \(k=i+1\) 成立, 证毕
那么根据结论，当 \(n=2 k\) 时，有
\(f_{2 k}=f_{k} f_{k+1}+f_{k-1} f_{k}=f_{k}\left(f_{k+1}+f_{k-1}\right)=f_{k}\left(2 f_{k+1}-f_{k}\right)\)
当 \(n=2 k+1\) 时，有
\(f_{2 k+1}=f_{k} f_{k}+f_{k+1} f_{k+1}=f_{k}^{2}+f_{k+1}^{2}\)
也就是说，我们可以通过递归求出 \(f_{\left\lfloor\frac{k}{2}\right\rfloor}\) 和 \(f_{\left\lfloor\frac{k}{2}\right\rfloor+1}\) 来得到 \(f_{k}\)
据此，可以通过快速倍增法通过分奇偶快速求出 \(f_n\)

时间复杂度：\(logn\)

代码

矩阵乘法

// Problem: 斐波那契前 n 项和
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/1305/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>
 
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
 
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

int n,m;
LL a[3][3]={{0,1,0},{1,1,1},{0,0,1}},f1[3]={1,1,1};
void mulself(LL a[3][3])
{
	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]*a[k][j])%m;
	memcpy(a,c,sizeof c);
}
void mul(LL f1[3],LL a[3][3])
{
	LL c[3]={0};
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			c[i]=(c[i]+f1[j]*a[j][i])%m;
	memcpy(f1,c,sizeof c);
}
int main()
{
    cin>>n>>m;
    n--;
    while(n)
    {
    	if(n&1)
    		mul(f1,a);
    	mulself(a);
    	n>>=1;
    }
    cout<<f1[2];
    return 0;
}

推式子

// Problem: 斐波那契前 n 项和
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/1305/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>
 
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
 
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

int n,m;
LL a[2][2]={{0,1},{1,1}},f1[2]={1,1};
void mulself(LL a[2][2])
{
	LL c[2][2]={0};
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
			for(int k=0;k<2;k++)
				c[i][j]=(c[i][j]+a[i][k]*a[k][j])%m;
	memcpy(a,c,sizeof c);
}
void mul(LL f1[2],LL a[2][2])
{
	LL c[2]={0};
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
			c[i]=(c[i]+f1[j]*a[j][i])%m;
	memcpy(f1,c,sizeof c);
}
int main()
{
    cin>>n>>m;
    n++;
    while(n)
    {
    	if(n&1)
    		mul(f1,a);
    	mulself(a);
    	n>>=1;
    }
    cout<<(f1[0]-1+m)%m;
    return 0;
}

快速倍增法

// Problem: 斐波那契前 n 项和
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/1305/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>
 
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
 
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

int n,m;
PLL f(int n)
{
	if(n==1)return {1,1};
	PLL t=f(n>>1);
	LL t1=t.fi,t2=t.se;
	LL f1=t1*(2*t2%m-t1+m)%m;
	LL f2=(t1*t1+t2*t2)%m;
	if(n&1)return {f2,(f1+f2)%m};
	return {f1,f2};
}
int main()
{
    cin>>n>>m;
    cout<<f(n+2).fi-1;
    return 0;
}

码农公寓

题目链接