愛ちゃんパスワード(フィボナッチ接頭辞和)

ACM問題セット:https://blog.csdn.net/weixin_39778570/article/details/83187443タイトルリンク:https://code.mi.com/problem/list/view?id=137&cid=7

            。       ，        A,B,C,D,mod,n     。 
      ：

F(1) = A, F(2) = BF(1)=A,F(2)=B
F(n) = F(n-1) * F(n-2) * C^D   (n >= 2) 
F(n)=F(n−1)⋅F(n−2)⋅C^D          (n>2)

           G(n)   （G(n) F(n)  n  ），            。
      ，     G(n)%mod
    。     6    ，     A, B, C, D, mod, n. (1<=A,B,C,D,mod,n<=1000000000)；
       2000.
------------------------------------------------------------------------------------------
	        
           
               
     n             
                 -1  
   C^D     ....
        fa+fb-n
fa a  
fb b   
(f*A*n) =  [fib(n), fib(n+1)]  0   
n:		1 2 3 4 5 6  7     （     ）
B	    0 1 1 2 3 5  8 13....    Fib...
     0 1 2 4	7 12 20	 sumA(n-1) = f(n+1)-1 = (f*A*n)[1]-1    0  

A       1 0 1 1 2 3  5  8
     1 1 2 3 5 8  13  sumB(n-1) = f(n) = (f*A*n)[0]

C^D     0 0 1 2 4 7  12
     0 0 1 3 7 14 26  sumC(n-1) =  sumA(n-1) + sumB(n-1) - n

code

#include 
#define ll long long
#define fo(i,j,n) for(register int i=j; i<=n; ++i)
using namespace std;
ll a,b,c,d,mod,n,x,MOD;
int q_pow(ll a, ll n){
	int ret = 1;
	while(n){
		if(n&1)ret = ret*a%mod;
		a = a*a%mod;
		n>>=1;
	}
	return ret%mod;
}
int phi(int n){
	int ans = n;
	for(int i=2; i<=sqrt(n); i++){
		if(n%i==0){
			ans = ans/i*(i-1);
			while(n%i==0)n/=i;
		}
	}
	if(n>1)ans = ans/n*(n-1);
	return ans;
}
void mul(int f[2], int a[2][2]){
	int c[2];
	memset(c,0,sizeof c);
	for(int j=0; j<2; j++){
		for(int k=0; k<2; k++){
			c[j] = (c[j] + (ll)f[k]*a[k][j])%MOD;
		}
	}
	memcpy(f,c,sizeof(c));
}
void mulself(int a[2][2]){
	int c[2][2];
	memset(c,0,sizeof(c));
	for(int i=0; i<2; i++){
		for(int j=0;j<2; j++){
			for(int k=0; k<2; k++){
				c[i][j] = (c[i][j]+(ll)a[i][k]*a[k][j])%MOD;
			}
		}
	}
	memcpy(a,c,sizeof(c));
}
void solve(){
	int f[2] = {0,1};
	int A[2][2] = {{0,1},{1,1}};
	int t = n; 
	for(;t;t>>=1){
		if(t&1)mul(f, A);
		mulself(A);
	} 
//	cout<
	ll fa = f[0] + MOD; // f(n+1) 
	ll fb = f[1]-1 + MOD; // f(n+2)-1,              1 
	ll fc = fa + fb - n % MOD + MOD; //       C^D      fa+fb-n 
	c = q_pow(c, d%MOD+MOD); // C^D
	ll ans = q_pow(a,fa)%mod * q_pow(b,fb)%mod * q_pow(c,fc)%mod; 
	printf("%09d
",ans);
} 
int main(){
	while(cin>>a>>b>>c>>d>>mod>>n){
		MOD = phi(mod);
		solve();
	}
	return 0;
}