每日归档： 2019年3月21日

$$f_{i}=f_{i-1}+a_{i}^2$$
$$a_{i}^2=(xa_{i-1}+ya_{i-2})^2=(x^2a_{i-1}^2+2xya_{i-1}a_{i-2}+y^
2a_{i-2}^2)$$
$$a_{i}a_{i-1}=(xa_{i-1}+ya_{i-2})a_{i-1}=xa_{i-1}^2+ya_{i-1}a_{i-2}$$
故而我们就可以用矩阵加速递推来求这个函数的值。
我们弄出一个如下的基本矩阵：
$$ \left[\begin{matrix}a_{1}^2&a_{2}^2&a_{1}a_{2}&f_{2}\end{matrix}\right]$$
我们不妨将它看作一个四项式，则其中每一项的答案都可以从上述公式推得。故而可以得到这样一个矩阵：
$$ \left[\begin{matrix}0&y^2&0&y^2\\1&x^2&x&x^2\\0&2xy&y&2xy\\0&0&0&1\end{matrix}\right]$$
拿来矩阵快速幂一下即可。

#include<iostream>
#include<cstdio>


typedef long long ll;
const ll MOD=1000000007;

struct Mat{
	ll a[4][4];
	inline void init(){
		for(int i=0;i<4;++i){
			for(int j=0;j<4;++j){
				a[i][j]=0;
			}
		}
	}
	inline Mat operator*(const Mat &B)const{
		Mat C;
		C.init();
		for(int i=0;i<4;++i){
			for(int j=0;j<4;++j){
				for(int k=0;k<4;++k){
					C.a[i][j]=(C.a[i][j]+a[i][k]*B.a[k][j])%MOD;
				}
			}
		}
		return C;
	}
};
ll a1,a2,n,x,y;
void init(){
	scanf("%lld%lld%lld%lld%lld",&n,&a1,&a2,&x,&y);
	if(n==1){
		printf("%lld\n",a1*a1%MOD);
		return;
	}
	if(n==2){
		printf("%lld\n",(a2*a2+a1*a1)%MOD);
	}
	Mat BS,T;
	BS.init(),T.init();
	BS.a[0][0]=a1*a1%MOD,BS.a[0][1]=a2*a2%MOD,BS.a[0][2]=a1*a2%MOD,BS.a[0][3]=(BS.a[0][0]+BS.a[0][1])%MOD;
	T.a[0][0]=0,T.a[0][1]=y*y%MOD,T.a[0][2]=0,T.a[0][3]=y*y%MOD;
	T.a[1][0]=1,T.a[1][1]=x*x%MOD,T.a[1][2]=x,T.a[1][3]=x*x%MOD;
	T.a[2][0]=0,T.a[2][1]=2*x*y%MOD,T.a[2][2]=y,T.a[2][3]=2*x*y%MOD;
	T.a[3][0]=0,T.a[3][1]=0,T.a[3][2]=0,T.a[3][3]=1;
	n-=2;
	while(n){
		if(n&1){
			BS=BS*T;
		}
		T=T*T;
		n>>=1;
	}
	printf("%lld\n",BS.a[0][3]);
}

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		init();
	}
	return 0;
}