P7385 「EZEC-6」跳一跳 题解

请先阅读Ecrade_的文章中Subtask4,5的思路
题目:P7385 「EZEC-6」跳一跳
此题数据范围极大,为了优化时间复杂度,采用矩阵快速幂
根据Ecrade_的推理可知:
{ S [ n ]          = 1 × S [ n − 1 ] + f ′ [ n ] + ( 2 b ) n f ′ [ n + 1 ] = 0 × S [ n − 1 ] + ( a + b ) × f ′ [ n ] + a × ( 2 b ) n ( 2 b ) n + 1      = 0 × S [ n − 1 ] + 0 × f ′ [ n ] + 2 b × ( 2 b ) n \begin{cases}S[n]\ \ \ \ \ \ \ \ =1× S[n-1]+f^{'}[n]+(2b)^n \\ f^{'}[n+1]=0×S[n-1]+(a+b)×f^{'}[n]+a×(2b)^n\\ (2b)^{n+1\ \ \ \ }=0×S[n-1]+0×f^{'}[n]+2b×(2b)^n\end{cases} S[n]        =1×S[n1]+f[n]+(2b)nf[n+1]=0×S[n1]+(a+b)×f[n]+a×(2b)n(2b)n+1    =0×S[n1]+0×f[n]+2b×(2b)n
得式子:
[ S [ n ] f [ n + 1 ] ( 2 b ) n + 1 ] = [ 1 1 1 0 a + b a 0 0 2 b ] × [ S [ n − 1 ] f ′ [ n ] ( 2 b ) n ] \begin{bmatrix}S[n]\\f[n+1]\\(2b)^{n+1} \end{bmatrix}=\begin{bmatrix}1&1&1\\0&a+b&a\\0&0&2b\end{bmatrix}×\begin{bmatrix}S[n-1]\\f^{'}[n]\\(2b)^n\end{bmatrix} S[n]f[n+1](2b)n+1=1001a+b01a2b×S[n1]f[n](2b)n
                      = [ 1 1 1 0 a + b a 0 0 2 b ] n − 1 × [ S [ 1 ] f ′ [ 2 ] ( 2 b ) 2 ] \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\begin{bmatrix}1&1&1\\0&a+b&a\\0&0&2b\end{bmatrix}^{n-1}×\begin{bmatrix}S[1]\\f^{'}[2]\\(2b)^2\end{bmatrix}                      =1001a+b01a2bn1×S[1]f[2](2b)2
[ 1 1 1 0 a + b a 0 0 2 b ] \begin{bmatrix}1&1&1\\0&a+b&a\\0&0&2b\end{bmatrix} 1001a+b01a2b A A A,则有 [ S [ n ] f [ n + 1 ] ( 2 b ) n + 1 ] = A n × [ a + b × 2 ( a + b ) × a + a × b × 2 4 b 2 ] \begin{bmatrix}S[n]\\f[n+1]\\(2b)^{n+1} \end{bmatrix}=A^n×\begin{bmatrix}a+b×2\\(a+b)×a+a×b×2\\4b^2\end{bmatrix} S[n]f[n+1](2b)n+1=An×a+b×2(a+b)×a+a×b×24b2
B B B储存 A n A^n An最终得到式子:
S [ n ] = B [ 1 ] [ 1 ] ∗ ( a + b × 2 ) + B [ 1 ] [ 2 ] [ ( a + b ) × a + a × b × 2 ] + B [ 1 ] [ 2 ] × 4 b 2 S[n]=B[1][1]*(a+b×2)+B[1][2][(a+b)×a+a×b×2]+B[1][2]×4b^2 S[n]=B[1][1](a+b×2)+B[1][2][(a+b)×a+a×b×2]+B[1][2]×4b2

Code:

#include
#define ll unsigned long long 
using namespace std;
const ll p=1000000007;
inline ll Read(){
     
	ll dx=0,fh=1;
	char c=getchar();
	while(c>'9'||c<'0'){
     
		if(c=='-')	fh=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
     
		dx=dx*10+c-'0';
		c=getchar();
	}
	return dx*fh;
}
ll quick_pow(ll x,ll y){
     
	ll r=1,base=x,yy=y;
	while(y){
     
		if(y&1)	r=(r*base)%p;
		base=(base*base)%p;
		y>>=1;
	}
	return r%p;
}
ll n,a,b,m,spe;
struct Matricx{
     
	ll val[5][5];
};
Matricx Mul(Matricx x,Matricx y){
     
	Matricx Ans;
	for(int i=1;i<=4;++i)
		for(int j=1;j<=4;++j){
     
			Ans.val[i][j]=0;
			for(int k=1;k<=4;++k)	Ans.val[i][j]=(Ans.val[i][j]+((x.val[i][k]%p)*(y.val[k][j]%p))%p)%p;
			Ans.val[i][j]%=p;
		}
	return Ans;
}
Matricx quickpow(Matricx x,ll y){
     
	Matricx r,base=x;
	for(int i=1;i<=4;++i){
     
		for(int j=1;j<=4;++j)	r.val[i][j]=0;
		r.val[i][i]=1;
	}
	while(y){
     
		if(y&1) r=Mul(r,base);
		base=Mul(base,base);
		y>>=1;
	}
	return r;
}
Matricx A,B;
int main(){
     
	n=Read(),a=Read(),b=Read(),m=Read();
	a=a*570000004%p,b=b*570000004%p;
	for(int i=1;i<=m;++i){
     
		ll spe_num=Read(),spe_score=Read();
		spe=(spe+quick_pow(a+b,spe_num-1)*b%p*spe_score%p)%p;
	}
	A.val[1][1]=1,A.val[1][2]=1,A.val[1][3]=1;
	A.val[2][1]=0,A.val[2][2]=a+b,A.val[2][3]=a;
	A.val[3][1]=0,A.val[3][2]=0,A.val[3][3]=2*b;
	B=quickpow(A,n-1);
	ll s1=(a+b*2)%p,f2=( ((a+b)*a)%p + (a*b*2)%p  )%p;
	printf("%u\n",(((B.val[1][1]*s1%p + B.val[1][2]*f2%p)%p + B.val[1][3]*((4*b*b)%p)%p)%p +spe%p)%p);
	return 0;
}

记住打完代码后一定要检查一下每个式子有没有漏取模!本人因为这玩意从早上九点查到了下午三点半!

你可能感兴趣的