LGP1397题解

并不是那么的有意思呢

首先，我们可以将题目给出的地推式看做一个一次函数 $k * x+b$，来思考一个问题，如果给出两个一次函数 $F(x)$ 和 $G(x)$，那么 $F(G(x))$ 是什么？

设 $F(x)=a * x+b,G(x)=c * x+d$，那么 $F(G(x))=(a * c) * x+(a * d+b)$，可以发现其仍然是一个一次函数。

可以知道一定存在一个 $F(x)$，使 $f[n][m]=F(f[n][1])$。设题目给出的第一个函数是 $f$，第二个是 $g$，那么很明显有 $F(x)=f^{n-1}(x)$。（这里的指数表示有 $n-1$ 层嵌套）

那么怎么算 $f^n(x)$ 呢？打个表：

\[a(a(ax+b)+b)+b=a^3x+a^2b+ab+b=a^3x+(\sum_{i=0}^{3-1}a)b
\]

上面是 $n$ 为 3 的情况。

于是就有了：

\[f^n(x)=a^nx+(\frac {a^n-1} {a-1})b
\]

记得特判 $ n=1 $ 的情况，分情况对 $1000000007$ 和 $1000000006$ 取模。

于是可以得到 $f[n][m]$ 与 $f[n][1]$ 的关系，同理可以得到 $f[n+1][1]=G(f[n][1]),f[n][1]=H(f[1][1])$ 以及 $f[n][m]=T(f[1][1])$。

根本不需要那么麻烦的一车特判。

喜闻乐见的代码片段：

#include<cstdio>

#include<cctype>

typedef unsigned ui;

const ui mod=1e9+7,MOD=mod-1;

ui n,m,x,y,T;

inline ui pow(ui a,ui b=mod-2){

	ui ans(1);

	for(;b;b>>=1,a=1ull*a*a%mod)if(b&1)ans=1ull*ans*a%mod;

	return ans;

}

struct func{

	ui k,b;

	func(const ui&k=0,const ui&b=0):k(k),b(b){}

	inline ui operator()(const ui&x){

		return (1ull*k*x+b)%mod;

	}

	inline func operator()(const func&it)const{

		return func(1ull*k*it.k%mod,(1ull*k*it.b+b)%mod);

	}

	inline func pow(const ui&x)const{

		return k==1?func(k,1ull*b*x%mod):func(::pow(k,x),1ull*(::pow(k,x)-1)*::pow(k-1)%mod*b%mod);

	}

}a,b;

inline ui read(){

	ui n(T=0);char s;while(!isdigit(s=getchar()));

	while(n=(10ull*n+(s&15))%MOD,T=(10ull*T+(s&15))%mod,isdigit(s=getchar()));

	return n;

}

signed main(){

	ui i;n=read();x=T;m=read();y=T;a.k=read();a.b=read();b.k=read();b.b=read();

	a=a.pow(a.k==1?y-1:m-1);b=b(a);printf("%u",a(b.pow(b.k==1?x-1:n-1))(1));

}

巴特西

LGP1397题解

最新文章

热门文章