矩阵快速幂-CodeForces 450B Jzzhu and Sequences 题目：
Jzzhu has invented a kind of sequences, they meet the following property:
文章图片
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).
Examples
Input
2 3
3
Output
1
Input
0 -1
2
Output
1000000006
Note
In the first sample, f2?=?f1?+?f3, 3?=?2?+?f3, f3?=?1.
In the second sample, f2?=??-?1;
?-?1 modulo (109?+?7) equals (109?+?6).
题意：
满足上述递推式，输入f1和f2，再输入n，求fn=？
【矩阵快速幂-CodeForces 450B Jzzhu and Sequences】思路：
矩阵快速幂的模板题。
递推式满足：
文章图片
记关系矩阵为T=
文章图片
，
An=
文章图片
，
那么由T*A(n-1)=A(n) 容易得到A(n)=T(n-1) *A(1)，于是问题只需求解矩阵Tn-1即可。
理解矩阵快速幂，先来看一看整数的快速幂：
int quieck_pow(ll a, int n)
{
ll ans = 1;
while (n) {
if (n & 1) ans = ans * a ;
//n是奇数，就更新一次最终的ans
a = a * a ;
//底数a变为a^2
n >>= 1;
//指数n/2
}
returnans;
}
也就是将an不断分解为(a(n/2))2来计算，时间复杂度从O(n)变成了O(logn)。
再来看矩阵快速幂：
ll s[N][N] = {1, 0, 0, 1};
//单位矩阵
void mat_pow(int n) //矩阵快速幂A^n
{
ll x[N][N] = {0, 1, -1, 1};
while (n) {
if (n&1)
mat_mod(s, x);
//单位矩阵s可类比上述整数快速幂中ans=1
mat_mod(x, x);
n >>= 1;
}
}
本题代码：
#include
#include using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const int N=2;
//矩阵阶数
ll s[N][N] = {1, 0, 0, 1};
//单位矩阵void mat_mod (ll a[N][N], ll b[N][N])//矩阵乘法A*A
{
ll c[N][N];
memset(c, 0, sizeof(c));
for (int k = 0;
k < N;
k++) {
for (int i = 0;
i < N;
i++)
for (int j = 0;
j < N;
j++)
c[i][j] = ((c[i][j] + a[i][k] * b[k][j]) % mod + mod) % mod;
}
memcpy(a, c, sizeof(c));
}void mat_pow(int n) //矩阵快速幂A^n
{
ll x[N][N] = {0, 1, -1, 1};
while (n) {
if (n&1)
mat_mod(s, x);
mat_mod(x, x);
n >>= 1;
}
}int main () {
int x, y, n;
scanf("%d%d%d", &x, &y, &n);
if (n == 1)
printf("%lld\n", (x % mod + mod) % mod);
else {
mat_pow(n-2);
printf("%lld\n", ((x * s[1][0] % mod + y * s[1][1] % mod) % mod + mod) % mod);
}
return 0;
}
当然，如果是考试比赛现场，能偷鸡也是极好的。
不难发现其中的规律，周期是6，对负数取模做个特殊处理即可。
#include
#include
#define ll long long
using namespace std;
const int N=1e7;
const ll mod=1e9+7;
ll a[N];
ll n;
int main()
{
cin>>a[1]>>a[2];
for(int i=3;
i<=6;
i++)
a[i]=a[i-1]-a[i-2];
a[0]=a[6];
//注意取模范围为0~5，需要给a[0]赋值
scanf("%lld",&n);
if(a[n%6]<0)//负数取模
{
while(a[n%6]<0)
a[n%6]+=mod;
printf("%lld\n",a[n%6]);
}
else
printf("%lld\n",a[n%6]%mod);
return 0;
}
