暴力解法。
初学群论，可能写的不是很严谨，望大佬指正。
problem
\[g^{(n)}(x)=\begin{cases} x,&(n=0).\\ f(g^{(n-1)}),&(n>0). \end{cases}\]其中 \(f\) 是一次函数。给出 \(f\) 的表达式与 \(n,x\)，求 \(g^{(n)}(x)\)。\(n\leq 10^{18}\)，答案对 \(P\) 取模。
solution
对于两个整式（这里指单项式与多项式的合称） \(f,g\)，我们定义它们的复合 \((f*g)(x)=f(g(x)).\) 其中 \(*\) 是我们自己定义的对于两个整式的二元运算。
则 \(g^{(n)}=f*g^{(n-1)}=f*f*g^{(n-2)}=\cdots=\begin{matrix}n\text{ 个 }f\\\overbrace{f*f*\cdots*f}*id\end{matrix}.\) 其中 \(id(x)=g^{(0)}(x)=x.\)
我们注意到 \(f,h\) 都是一次函数，这非常方便。
下面证明：
两个一次函数复合后仍为一次函数。
证明 令 \(f(x)=kx+b,g(x)=k'x+b'\)，则 \(f*g=f(g(x))=k(k'x+b)+b'=(k\cdot k')x+(kb+b').\)
整式的复合具有结合律：\((f*g)*h=f*(g*h)\)。
证明 \(LHS=RHS=f(g(h(x))).\)
\(*\) 运算的单位元是 \(id\)。
证明 \((f*id)(x)=f(id(x))=f(x),(id*f)(x)=id(f(x))=f(x).\)
因为 \(*\) 有单位元和结合律，于是我们可以用一种类似于快速幂的方法，求出 \(f\) 自己复合自己 \(n\) 次后的结果，代入 \(x\) 即可。\(O(\log n)\)。
因为快速幂只依赖于一个单位元和结合律，这也是矩阵快速幂可行所在。若将文中 \(f\) 换为矩阵，也可以用这样的方法分析出快速幂的正确性。
code
点击查看代码
typedef long long LL;
const int P=1e9+7;
struct func{
LL k,b;
func(LL k=1,LL b=0):k(k),b(b){}
func operator*(func g){
//k(k'x+b')+b
return func(k*g.k%P,(k*g.b+b)%P);
}
LL operator()(LL x){return (k*x+b)%P;}
};
template<class T> T qpow(T a,LL b){
T r=func(1,0);
for(;b;a=a*a,b>>=1) if(b&1) r=r*a;
return r;
}
LL n,A,B,x;
int main(){
scanf("%lld%lld%lld%lld",&A,&B,&n,&x);
printf("%lld\n",qpow(func(A,B),n)(x));
return 0;
}