【算法】矩阵快速幂
【题解】T*A(n-1)=A(n)矩阵如下：
a 1 * x(n-1) 0 = xn 0
0 1 c 0 c 0
防止溢出可以用类似快速幂的快速乘。
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
ll MOD,A,c,x0,n,g,a[][],b[][],t[][];
ll mull(ll x,ll y)
{
ll ans=;
while(y>)
{
if(y&)ans=(ans+x)%MOD;
x=(x<<)%MOD;//x+x
y>>=;
}
return ans;
}
void mul(ll a[][],ll b[][],ll ans[][])
{
for(int i=;i<;i++)
for(int j=;j<;j++)
{
t[i][j]=;
for(int k=;k<;k++)
t[i][j]=(t[i][j]+mull(a[i][k],b[k][j]))%MOD;
}
for(int i=;i<;i++)
for(int j=;j<;j++)
ans[i][j]=t[i][j];
}
int main()
{
scanf("%lld%lld%lld%lld%lld%lld",&MOD,&A,&c,&x0,&n,&g);
a[][]=A,a[][]=a[][]=,a[][]=;
b[][]=x0,b[][]=c,b[][]=b[][]=;
while(n>)
{
if(n&)mul(a,b,b);
n>>=;
mul(a,a,a);
}
printf("%lld",b[][]%g);
return ;
}