Sequence
\ \ \ \ Holion August will eat every thing he has found.
\ \ \ \ Now there are many foods,but he does not want to eat all of them at once,so he find a sequence.
f_n=\left{\begin{matrix} 1 ,&n=1 \ a^b,&n=2 \ a^bf_{n-1}^cf_{n-2},&otherwise \end{matrix}\right.fn=⎩⎨⎧1,ab,abfn−1cfn−2,n=1n=2otherwise
\ \ \ \ He gives you 5 numbers n,a,b,c,p,and he will eat f_nfn foods.But there are only p foods,so you should tell him f_nfn mod p.
\ \ \ \ The first line has a number,T,means testcase.
\ \ \ \ Each testcase has 5 numbers,including n,a,b,c,p in a line.
\ \ \ \ 1\le T \le 10,1\le n\le 10^{18},1\le a,b,c\le 10^9 1≤T≤10,1≤n≤1018,1≤a,b,c≤109,pp is a prime number,and p\le 10^9+7p≤109+7.
\ \ \ \ Output one number for each case,which is f_nfn mod p.
1
5 3 3 3 233
190
/*
hdu 5667 BestCoder Round #80 矩阵快速幂 F[n] = 1 (n == 1)
F[n] = a^b (n == 2)
F[n] = a^b * F[n-1]^c *F [n-2] 最开始试了下化简公式,但是无果. 也从矩阵快速幂上面考虑过(毕竟 F[n]与 F[n-1],F[n-2]有关)
但是发现是 乘法运算不知道怎么弄了(2b了) 能够发现运算时基于a的次方的,当a的次方相乘时就变成了他们的次方相加 (好气 TAT)
于是乎 a^g[n] = a^(b + c*g[n-1] * g[n-2])
然后用类似快速幂求斐波那契数的方法即可 F[n] F[n-1] 1 C 1 0
F[n-1] F[n-2] 1 * 1 0 0
b 0 1
hhh-2016-04-18 20:36:40
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <functional>
#include <math.h>
using namespace std;
#define lson (i<<1)
#define rson ((i<<1)|1)
typedef long long ll;
const int maxn = ; struct Matrix
{
ll ma[][];
Matrix()
{
memset(ma,,sizeof(ma));
}
}; Matrix mult(Matrix ta,Matrix tb, ll mod)
{
Matrix tc;
for(int i = ; i < ; i++)
{
for(int j = ; j < ; j++)
{
tc.ma[i][j] = ;
for(int k = ; k < ; k++){
tc.ma[i][j] += (ta.ma[i][k] * tb.ma[k][j])%mod;
tc.ma[i][j] %= mod;
}
}
}
return tc;
} Matrix Mat_pow(Matrix ta,ll n,ll mod)
{
Matrix t;
for(int i = ; i < ; i++)
t.ma[i][i] = ;
while(n)
{
if(n & ) t = mult(t,ta,mod);
ta = mult(ta,ta,mod);
n >>= ;
}
return t;
} ll pow_mod(ll a,ll n,ll mod)
{
ll t = ;
a %= mod ;
while(n)
{
if(n & ) t = t*a%mod;
a = a*a%mod;
n >>= ;
}
return t;
} Matrix mat;
Matrix an;
ll a,b,c;
void ini(ll mod)
{
mat.ma[][] = c,mat.ma[][] = ,mat.ma[][] = ;
mat.ma[][] = ,mat.ma[][] = ,mat.ma[][] = ;
mat.ma[][] = b,mat.ma[][] = ,mat.ma[][] = ; an.ma[][] = (b+b*c%mod)%mod,an.ma[][] = b,an.ma[][] = ;
an.ma[][] = b,an.ma[][] = ,an.ma[][] = ;
}
ll mod,n; int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%I64d%I64d%I64d%I64d%I64d",&n,&a,&b,&c,&mod);
a%=mod,b%=mod,c%=mod;
ini(mod-);
if(n == )
{
printf("1\n");
}
else if(n == )
printf("%I64d\n",pow_mod(a,b,mod));
else
{
mat = Mat_pow(mat,n-,mod-);
mat = mult(an,mat,mod-);
ll ci = mat.ma[][];
//cout << ci <<endl;
printf("%I64d\n",pow_mod(a,ci,mod));
}
}
return ;
}