数学 找规律 Jzzhu and Sequences

A - Jzzhu and Sequences

 

Jzzhu has invented a kind of sequences, they meet the following property:

You are given x and y, please calculate f modulo 1000000007 (10 + 7).

Input

The first line contains two integers x and y (|x|, |y| ≤ 10). The second line contains a single integer n (1 ≤ n ≤ 2·10).

Output

Output a single integer representing f modulo 1000000007 (10 + 7).

Example

Input

2 3
3

Output

1

Input

0 -1
2

Output

1000000006

Note

In the first sample, f = f + f, 3 = 2 + f, f = 1.

In the second sample, f =  - 1;  - 1 modulo (10 + 7) equals (10 + 6).

第一次用矩阵快速幂 做不出来 可能是因为N太大了

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<sstream>

#include<algorithm>

#include<queue>

#include<deque>

#include<iomanip>

#include<vector>

#include<cmath>

#include<map>

#include<stack>

#include<set>

#include<fstream>

#include<memory>

#include<list>

#include<string>

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

#define MAXN 50000

#define N 21

#define MOD 1000000007

#define INF 1000000009

const double eps = 1e-;

const double PI = acos(-1.0);

//斐波那契数列求第N项

struct Mat

{

    LL data[][];

    Mat(LL d1, LL d2, LL d3, LL d4)

    {

        data[][] = d1, data[][] = d2, data[][] = d3, data[][] = d4;

    }

    Mat operator*(const Mat& rhs)

    {

        Mat result(,,,);

        result.data[][] = (data[][] * rhs.data[][] + data[][] * rhs.data[][]+ MOD )%MOD;

         result.data[][] = (data[][] * rhs.data[][] + data[][] * rhs.data[][]+ MOD )%MOD;

        result.data[][] = (data[][] * rhs.data[][] + data[][] * rhs.data[][]+ MOD )%MOD;

        result.data[][] = (data[][] * rhs.data[][] + data[][] * rhs.data[][]+ MOD )%MOD;

        return result;

    }

};

void Print(const Mat& tmp)

{

    cout << tmp.data[][] << ' ' << tmp.data[][] << endl;

    cout << tmp.data[][] << ' ' << tmp.data[][] << endl << endl;

}

Mat fpow(Mat a, LL b)

{

    Mat tmp = a, ret(,,,);

    while (b != )

    {

        //Print(ret);

        if (b & )

            ret = tmp*ret;

        tmp = tmp*tmp;

        b /= ;

    }

    //Print(ret);

    return ret;

}

int main()

{

    LL x, y, n;

    while (cin >> x >> y >> n)

    {

        if (n == )

            cout << (x + MOD) % MOD << endl;

        else if (n == )

            cout << (y + MOD) % MOD << endl;

        else

        {

            Mat m = fpow(Mat(, -, , ), n - );

            cout << (m.data[][] * y + m.data[][] * x + MOD) % MOD << endl;

        }

    }

}

其实一个滚动数组即可解决

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<sstream>

#include<algorithm>

#include<queue>

#include<deque>

#include<iomanip>

#include<vector>

#include<cmath>

#include<map>

#include<stack>

#include<set>

#include<fstream>

#include<memory>

#include<list>

#include<string>

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

#define MAXN 50000

#define N 21

#define MOD 1000000007

#define INF 1000000009

const double eps = 1e-;

const double PI = acos(-1.0);

LL a[N];

int main()

{

    LL x, y, n;

    while (cin >> x >> y >> n)

    {

        a[] = (x + MOD) % MOD;

        a[] = (y + MOD) % MOD;

        for (int i = ; i < ; i++)

            a[i] = (a[i - ] - a[i - ] + MOD) % MOD;

        cout << (a[(n - ) % ] + MOD) % MOD << endl;

    }

}