CodeForces 450B Jzzhu and Sequences （矩阵优化）

594 0 0

作者:SYCstudio

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

Input

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

Sample Input

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;
}

内容来源于网络如有侵权请私信删除

标签：算法数据结构

你还没有登录，请先登录或注册！

还没有人评论，欢迎说说您的想法！

CodeForces 450B Jzzhu and Sequences （矩阵优化）