CodeForces 450B Jzzhu and Sequences （矩阵优化）
Description
Jzzhu has invented a kind of sequences, they meet the following property:\[f_1=x\]\[f_2=y\]\[f_i=f_{i-1}+f_{i+1}\text {(i>2)}\] You are given x and y, please calculate fn modulo 1000000007 (109 + 7).
The first line contains two integers x and y (|x|, |y| ≤ 109). The second line contains a single integer n (1 ≤ n ≤ 2·109).
Output
Output a single integer representing fn modulo 1000000007 (109 + 7).
Input1: 2 3 3 Input2: 0 -1 2
Sample Output
Output1: 1 Output2: 1000000006
Http
CodeForces:https://vjudge.net/problem/CodeForces-450B
Source
矩阵，递推
题目大意
给定f1和f2，要按照\[f_i=f_{i-1}+f_{i+1}\text {(i>2)}\]求出fn
解决思路
刚看到递推式子的时候有些摸不着头脑，这个要推出fi要先推出fi-1和fi+1，怎么做呢？ 其实很简单，把式子变一下形：\[f_{i+1}=f_i-f_{i-1}\] 于是我们就得到：\[f_i=f_{i-1}-f_{i-2}\] 当然，看到题目的数据范围，直接这么傻推是不行的，我们要用矩阵优化！ 关于矩阵的基本内容请到我的这一篇文章阅读。 经过推理，我们可以得到本题的转移矩阵T是:\[T=\begin{bmatrix} 1 & 1 \\ -1 & 0 \end{bmatrix}\] 然后直接用矩阵快速幂就可以了。 最后要注意的一点就是，题目中给出的x和y都有可能是负数，并且求解过程中也有可能出现负数（因为有减法操作嘛），所以在取膜的时候，要先+Mod，再%Mod（具体请看代码中，已经标记出来了）
代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long//为了防止越界，统一全部用long long存
const ll Mod=1000000007;
class Matrix//定义一个矩阵结构体
{
public:
ll A[2][2];
Matrix()//初始化。为了方便下面的运算，这里定义两种初始化，一种是直接全部为０，另一种是用一个二维数组给定其初值
{
memset(A,0,sizeof(A));
}
Matrix(ll arr[2][2])
{
for (int i=0;i<2;i++)
for (int j=0;j<2;j++)
A[i][j]=arr[i][j];
}
};
Matrix operator * (Matrix A,Matrix B)//重载乘法运算
{
Matrix Ans;
for (int i=0;i<2;i++)
for (int j=0;j<2;j++)
for (int k=0;k<2;k++)
Ans.A[i][j]=(Ans.A[i][j]+(A.A[i][k]*B.A[k][j]+Mod)%Mod+Mod)%Mod;//注意这里的取膜操作，防止了负数越界
return Ans;
}
int main()
{
ll x,y,n;
cin>>x>>y>>n;
x=(x+Mod)%Mod;//这里因为x和y再输入的时候就有可能是负数（比如样例２），所以先取一次膜
y=(y+Mod)%Mod;
if (n==1)//ｎ为１和２的时候直接输出
{
cout<<x<<endl;
return 0;
}
if (n==2)
{
cout<<y<<endl;
return 0;
}
ll a[2][2]={{y,x},{0,0}};
ll b[2][2]={{1,1},{-1,0}};
Matrix A(a);
Matrix B(b);
n=n-2;//这里要-2是因为1和2的已经处理了，现在只要乘以n-2次
while (n!=0)//矩阵快速幂
{
if (n&1)
A=A*B;
B=B*B;
n=n>>1;
}
cout<<A.A[0][0]<<endl;
return 0;
}
转载于:https://www.cnblogs.com/SYCstudio/p/7212329.html
相关资源：JAVA上百实例源码以及开源项目
