uoj124 矩阵游戏

发表于 | 更新于

Link

Solution

化简一下式子，比较简单，只用到了等比数列的知识 化简出来之后，发现是当 的时候，是几个幂乘一乘加一加，而这些数字都是小于模数的，所以一定与模数互质，用费马小定理优化即可。 有一个坑点： 当a==1a==1的时候，求和的式子里面就没有幂了！所以只能先把nn存起来，然后分开讨论！

Tips

看一个式子是否满足适用条件，要循环地展开下去查看是否满足

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
//Code by Lucida
#include<bits/stdtr1c++.h>
#define get(x) scanf("%d",&x)
#define put(x) printf("%d",x)
typedef long long int64;
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int P=1000000007,MAXN=1e3+11,MAXL=1e6+11;

template <class T> T Pow(T base,int index)
{
	T res;
	for(res.SetI();index;base*=base,index>>=1)
		if(index&1) res*=base;
	return res;
}
struct ModInt
{
	int num;
	ModInt(int x=0):num(x%P){}
	ModInt inv() {return Pow(*this,P-2);}
	ModInt &operator =(int x){return *this=ModInt(x);}
	ModInt &operator +=(ModInt a){num=((int64)num+a.num)%P;return *this;}
	ModInt &operator -=(ModInt a){num=((int64)num-a.num)%P;return *this;}
	ModInt &operator *=(ModInt a){num=((int64)num*a.num)%P;return *this;}
	ModInt &operator /=(ModInt a){return (*this)*=a.inv();}
	ModInt &operator +=(int a){return *this+=ModInt(a);}
	ModInt &operator -=(int a){return *this-=ModInt(a);}
	ModInt &operator *=(int a){return *this*=ModInt(a);}
	ModInt &operator /=(int a){return *this/=ModInt(a);}
	void SetI(){num=1;}
	int Num(){return (num+P)%P;}
};
template<class T> ModInt operator +(ModInt a,const T& b){a+=b;return a;}
template<class T> ModInt operator -(ModInt a,const T& b){a-=b;return a;}
template<class T> ModInt operator *(ModInt a,const T& b){a*=b;return a;}
template<class T> ModInt operator /(ModInt a,const T& b){a/=b;return a;}
int atoi_mod(char *ip,int modu)
{
	bool f;char ch;int x;
	for(f=0,ch=0;ch<'0' || '9'<ch;ch=*ip++) f|=ch=='-';
	for(x=0;'0'<=ch && ch<='9';ch=*ip++) x=((int64)x*10+ch-'0')%modu;
	x=f?modu-x:x;x=x==0?modu:x;return x;
}
char N[MAXL],M[MAXL];
int a,b,c,d;
struct Sequence
{
	int a,q;
	Sequence(int a,int q):a(a),q(q){}
	ModInt operator ()(int x) {return (Pow(ModInt(q),x)-1)*a/(q-1);}
};
int F()
{
	ModInt Ans=1,a=::a,b=::b,c=::c,d=::d,sam_1,ssn_1,s,t;
	int mp_1=atoi_mod(M,P-1),mp=atoi_mod(M,P),np_1=atoi_mod(N,P-1),np=atoi_mod(N,P);
	sam_1=a.Num()!=1?Sequence(1,a.Num())(mp_1-1):mp-1;
	s=c*Pow(a,mp_1-1),t=b*c*sam_1+d;
	ssn_1=s.Num()!=1?Sequence(1,s.Num())(np_1-1):np-1;
	Ans=Pow(s,np_1-1)+ssn_1*t;
	Ans=Pow(a,mp_1-1)*Ans+sam_1*b;
	return Ans.Num();
}

int main()
{
	scanf("%s%s",N,M);	
	get(a),get(b),get(c),get(d);
	put(F()),putchar('\n');
	return 0;
}