发布于

lp5175 数列

$$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;
}
发布于

lp2044 NOI2012 随机数生成器

我们不妨将原式递归展开，可以得到形如此的式子：
$$f_{n}=a^nf_{0}+\frac{(a^{n}-1)c}{a-1}$$
对于这个式子的值，我们看似可以上一个快速幂直接求得。
然而仔细观察上式的情况，发现如果出现了奇妙的模数时，\(a-1\)是不一定有逆元的！
这就很令人难受了。
我们找到原来的问题，我们不得不求下述式子的值：
$$f_{n}=a^nf_{0}+\sum_{i=0}^{n-1}a^ic=a^nf_{0}+(\sum_{i=0}^{n-1}a^i)c$$
求值的最大障碍是这个式子：
$$\sum_{i=0}^{n-1}a^i$$
将这个式子分奇偶讨论后递归求解。
我们令：
$$u_{x}=\sum_{i=0}^{x-1}a^i$$
若是偶数，则有：
$$u_x=\sum_{i=0}^{\frac{x-1}{2}}a^i+a^{\frac{x+1}{2}} (\sum_{i=0}^{\frac{x-1}{2}}a^i)$$
即，
$$u_x=(a^{\frac{x+1}{2}}+1)u_{\frac{x-1}{2}}$$
若是奇数，则只需将第一项单独计算。
这样就可以在对数复杂度内对式子求解了。
另外，考虑到模数的数据范围，我们需要使用一种被称为「龟速乘」，也就是「快速幂」在乘法意义上的等同的操作，使得不会出现乘法，也就不会爆范围。

#include<iostream>
#include<cstdio>

long long MOD,a,c,x0,n,g;
//必须注意，不能重载一个全部是标准型的运算符。 
inline long long mlt(long long A,long long X){
	long long BS=A,RT=0,CNT=X;
	while(CNT){
		if(CNT&1){
			RT+=BS;
			RT%=MOD;
		}
		CNT>>=1;
		BS+=BS;
		BS%=MOD;
	}
	return RT;
}
inline long long pw(long long A,long long X){
	long long BS=A,RT=1,CNT=X;
	while(CNT){
		if(CNT&1){
			RT=mlt(RT,BS)%MOD;
		}
		CNT>>=1;
		BS=mlt(BS,BS)%MOD;
	}
	return RT;
}
inline long long calc(long long X){
	if(X==2){
		return (a+1)%MOD;
	}
	if(X==1){
		return 1;
	}
	if(X&1){
		return (pw(a,X-1)+calc(X-1))%MOD;
	}
	return mlt((pw(a,(X+1)>>1)+1),calc(X>>1));
}
void init(){
	scanf("%lld%lld%lld%lld%lld%lld",&MOD,&a,&c,&x0,&n,&g);
	printf("%lld",((mlt(pw(a,n),x0)+mlt(calc(n),c))%MOD)%g);
}

int main(){
	init();
	return 0;
}