http://acm.hdu.edu.cn/showproblem.php?pid=2971對于：f[n]=a*f[n-1]+b*f[n-2]....這類線性變換，構(gòu)造變換矩陣，用矩陣乘法來做。
一般數(shù)會很大，結(jié)果mod一個整數(shù)。這里要注意變換矩陣中可能存在負(fù)數(shù)，需要求出關(guān)于mod的逆元來運(yùn)算。
總結(jié)：線性變換 矩陣乘法 TLE處理
using namespace std;
long long c,n;
long long mod;
long long mtx[5][5];
long long e[5][5];
long long tmp[5][5];
long long r[5];
long long temp[5];
void init()
{
mtx[1][1]=1;mtx[1][3]=1;
mtx[2][1]=0;mtx[2][3]=1;
mtx[3][1]=0;mtx[3][2]=1;
mtx[3][3]=0;mtx[3][4]=0;
mtx[4][1]=0;mtx[4][3]=0;
mtx[2][2]=mtx[1][2]=4*c*c % mod;
mtx[2][4]=mtx[1][4]=(mod-4*c % mod) % mod;
mtx[4][4]=mod-1;mtx[4][2]=2*c % mod;
return ;
}
void matrix_mul()
{
for (int i=1;i<=4;i++)
for (int j=1;j<=4;j++)
tmp[i][j]=mtx[i][j];
for (int i=1;i<=4;i++)
for (int j=1;j<=4;j++)
{
mtx[i][j]=0;
for (int k=1;k<=4;k++)
{
mtx[i][j]=(mtx[i][j]+tmp[i][k]*tmp[k][j]) % mod;
}
}
return ;
}
int main()
{
int t;
scanf("%d",&t);
while (t--)
{
scanf("%lld%lld%lld",&c,&n,&mod);
init();
r[1]=(c*c+1) % mod;r[2]=c*c % mod;
r[3]=1;r[4]=c % mod;
if (n==1)
{
printf("%lld\n",1 % mod);
continue;
}
if (n==2)
{
printf("%lld\n",r[1] % mod);
continue;
}
n-=2;
while (n)
{
if (n&1)
{
for (int i=1;i<=4;i++)
temp[i]=r[i];
for (int i=1;i<=4;i++)
{
r[i]=0;
for (int j=1;j<=4;j++)
{
r[i]=(r[i]+temp[j]*mtx[i][j]) % mod;
}
}
}
matrix_mul();
n>>=1;
}
printf("%lld\n",r[1] % mod);
}
return 0;
}