[Acwing] 1303. 斐波那契前 n 项和 矩阵快速幂

前言

在计算斐波那契数列的时候, F [ n ] = F [ n − 1 ] + F [ n − 2 ] F[n] = F[n-1]+F[n-2] F[n]=F[n−1]+F[n−2],因此 F [ n ] F[n] F[n]直接相关于 F [ n − 1 ] , F [ n − 2 ] F[n-1],F[n-2] F[n−1],F[n−2] , 因此我们只需要记录最近的两个斐波那契数列即可

因此我们定义 f ( n ) = [ F n , F n + 1 ] f(n)=[F_{n},F_{n+1}] f(n)=[Fn​,Fn+1​] (一个一行两列的矩阵 因此有 f ( n + 1 ) = [ F n + 1 , F n + 2 ] f(n+1) = [F_{n+1},F_{n+2}] f(n+1)=[Fn+1​,Fn+2​]

因此我们可以构造系数矩阵 A A A 完成两者的传递关系

A = [ 0 1 1 1 ] A =\begin{bmatrix} 0&1\\ 1&1 \end{bmatrix} A=[01​11​]

其实这个是可以一眼看出的 , 首先说明 C i j = ∑ k = 1 m A i m ∗ B m j C_{ij} =\sum_{k=1}^mA_{im}*B_{mj} Cij​=∑k=1m​Aim​∗Bmj​这是矩阵 A ∗ B A*B A∗B的公式,也就是当前的项为前一个的行乘后一个的列

因此 f ( n ) ∗ A = [ F n , F n + 1 ] ∗ [ 0 1 1 1 ] = [ F n ∗ 0 + F n + 1 ∗ 1 , F n ∗ 1 + F n + 1 ∗ 1 ] = [ F n + 1 , F n + F n + 1 ] = [ F n , F n + 2 ] f(n)*A =[F_n,F_{n+1}]*\begin{bmatrix} 0&1\\ 1&1 \end{bmatrix}=[F_n*0+F_{n+1}*1,F_n*1+F_{n+1}*1] =[F_{n+1},F_n+F_{n+1}]=[F_{n},F_{n+2}] f(n)∗A=[Fn​,Fn+1​]∗[01​11​]=[Fn​∗0+Fn+1​∗1,Fn​∗1+Fn+1​∗1]=[Fn+1​,Fn​+Fn+1​]=[Fn​,Fn+2​]

如果我们需要求第 n n n项, F n = F 0 ∗ A n F_n =F_0 * A^n Fn​=F0​∗An 因为矩阵没有交换律只有结合律, 也就满足 A n = A 1 ∗ A 2 ∗ A 4 . . . A_n =A_1*A_2*A_4... An​=A1​∗A2​∗A4​...

这是普通的求项,但是这题求的是前缀和

思路

同理我们令

F n = [ f n , f n + 1 , S n ] ( 这 里 的 F , f 和 上 面 的 不 一 样 了 , 和 y 总 讲 解 统 一 F_n = [f_n,f_{n+1},S_n](这里的F,f和上面的不一样了,和y总讲解统一 Fn​=[fn​,fn+1​,Sn​](这里的F,f和上面的不一样了,和y总讲解统一

F n + 1 = [ f n + 1 , f n + 2 , S n + 1 ] F_{n+1}= [f_{n+1},f_{n+2},S_{n+1}] Fn+1​=[fn+1​,fn+2​,Sn+1​]

我们同时考虑 F n ∗ A = F n + 1 F_n * A =F_{n+1} Fn​∗A=Fn+1​ 显然这个 A A A应该是一共 3 ∗ 3 3*3 3∗3的矩阵

首先考虑第一行的也就是 F n + 1 中 的 f n + 1 F_{n+1}中的f_{n+1} Fn+1​中的fn+1​ 由矩阵乘法可得这个数应该由 F n F_n Fn​第一行乘 A A A中第一列得到的

设 A A A的第一例为 x , y , z x,y,z x,y,z显然有方程 f n ∗ x + f n + 1 ∗ y + S n ∗ z = f n + 1 f_n*x+f_{n+1}*y+S_n*z=f_{n+1} fn​∗x+fn+1​∗y+Sn​∗z=fn+1​ 则 x = 0 , y = 1 , z = 0 x=0,y=1,z=0 x=0,y=1,z=0 (显然失智,滑稽

A = [ 0 1 0 1 1 1 0 0 1 ] A =\begin{bmatrix} 0&1&0\\ 1&1&1\\ 0&0&1\\ \end{bmatrix} A=⎣⎡​010​110​011​⎦⎤​

因此同理 F n = F 0 ∗ A n = F 1 ∗ A n − 1 F_n =F_0*A^n = F_1*A^{n-1} Fn​=F0​∗An=F1​∗An−1

Mycode

// 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)

//��һ�δ��Ϻ�վ֮�� ��Ϊʹ��#define int long long TLE���¿��˺ܾõ�ʱ�� ���˼���ģ��
//����ʹ�ø��ӵ�ģ��

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define IOS  ios::sync_with_stdio(false);
#define CIT  cin.tie(0);
#define COT  cout.tie(0);

#define ll long long
#define x first
#define y second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(),x.end()
#define Fup(i,a,b) for(int i=a;i=b;i--)

typedef priority_queue  Pri_m;
typedef pair pii;
typedef vector VI;
map mp;

const int N  = 3;
int n,m;
void mul(int c[],int a[],int b[][N]){
	int t[3] = {0};
	for(int i = 0;i>=1;
	}
	//计算完之后 F[1] = f_N , F_N+1,S_N
	cout