Codeforces #566 Div2 E. Product Oriented Recurrence

これは最初の一手を思いつけば簡単。
https://codeforces.com/contest/1182/problem/E

問題

漸化式F(x)は、F(x)=c^(2x-6)*F(x-1)*F(x-2)*F(x-3) mod (10^9+7)で定義される。
F(1),F(2),F(3),c,nが与えられているとき、F(n)を求めよ。

解法

掛け算が足し算になっていればトリボナッチ数列っぽい形になる。
10^9+7の原子根の一つが5なので、Log(x)を底を5とする対数関数とすると、
Log(F(x)) = (2x-6)*Log(c) + Log(F(x-1)) + Log(F(x-2)) + Log(F(x-3))
となる。
あとはLog(F(n))をいつもの行列累乗で求めて、F(n)=5^Log(F(n))を答えればよい。
Log(x)は離散対数を求める問題なのでBaby-Step Giant-Stepを使う。

ll N,F1,F2,F3,C;
ll mo=1000000007;

const int MAT=5;
ll G[MAT][MAT],G2[MAT][MAT];
void powmat(ll p,int n,ll a[MAT][MAT],ll r[MAT][MAT]) {
	int i,x,y,z;
	ll a2[MAT][MAT];
	FOR(x,n) FOR(y,n) a2[x][y]=a[x][y];
	FOR(x,n) FOR(y,n) r[x][y]=(x==y);
	while(p) {
		ll h[MAT][MAT];
		if(p%2) {
			FOR(x,n) FOR(y,n) h[x][y]=0;
			FOR(x,n) FOR(z,n) FOR(y,n) h[x][y] += (r[x][z]*a2[z][y]) % mo;
			FOR(x,n) FOR(y,n) r[x][y]=h[x][y]%mo;
		}
		FOR(x,n) FOR(y,n) h[x][y]=0;
		FOR(x,n) FOR(z,n) FOR(y,n) h[x][y] += (a2[x][z]*a2[z][y]) % mo;
		FOR(x,n) FOR(y,n) a2[x][y]=h[x][y]%mo;
		p>>=1;
	}
}

ll modpow(ll a, ll n = mo-2) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

int modlog(int g,int a) {  // return g^x=a mod a
	map<int,int> M;
	ll cur=1;
	int sq=sqrt(mo);
	int i;
	FOR(i,sq) {
		M[cur]=i;
		cur=cur*g%mo;
	}
	
	ll step=cur;
	cur=1;
	ll num=0;
	while(1) {
		ll x=a*modpow(cur)%mo;
		if(M.count(x)) return num+M[x];
		cur=cur*step%mo;
		num+=sq;
	}
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>F1>>F2>>F3>>C;
	
	F1=modlog(5,F1);
	F2=modlog(5,F2);
	F3=modlog(5,F3);
	C=modlog(5,C);
	mo--;
	
	G[0][1]=G[1][2]=G[2][0]=G[2][1]=G[2][2]=G[2][3]=1;
	G[3][3]=G[4][4]=1;
	G[3][4]=2*C%mo;
	powmat(N-3,5,G,G2);
	ll p=(F1*G2[2][0]+F2*G2[2][1]+F3*G2[2][2]+2*C*G2[2][3]+G2[2][4])%mo;
	mo++;
	cout<<modpow(5,p)<<endl;
	
	
}

まとめ

BSGS、昔はARCの最終問題で出たりしてたのに、いつのまにかDiv2の最終より前の問題で出てきて、1000人以上解くテクになったんだな。