Submission #9275

#	Time	Username	Problem	Language	Result	Execution time	Memory
9275		myungwoo	Phibonacci (kriii2_P)	C++14	1 / 4	0 ms	1088 KiB

P

#include<stdio.h>
#define mod 1000000007

typedef long long lld;

struct term {
	lld a, b;
	term operator* (const term& c){
		term k;
		k.a = a*c.b+b*c.a, k.b = b*c.b;
		k.a += a*c.a, k.b += a*c.a;
		return k;
	}
	term operator% (const lld c){
		term k;
		k.a%=c, k.b%=c;
		return k;
	}
}pn, pnk, dap;

struct MAT{
	lld m[2][2];
	MAT operator * (const MAT &ot)const{
		MAT ret={0, };
		int i, j, k;
		for (i=0;i<2;i++) for (j=0;j<2;j++) for (k=0;k<2;k++)
			ret.m[i][j] = (ret.m[i][j]+(lld)m[i][k]*ot.m[k][j]%mod)%mod;
		return ret;
	}
} P[40];

lld n, k;

template <class T>
T exp(T a, lld b){
	if(b==1)return a;
	T im=exp(a,b/2);
	im=im*im, im=im%mod;
	if(b%2)im=im*a, im=im%mod;
	return im;
}

lld fibo(lld n){
	MAT t ={1, 0, 0, 1};
	int i;
	for (i=0;i<40;i++) if ((n>>i)&1) t = t*P[i];
	return t.m[0][1];
}

int main(){
	lld i;
	MAT t ={1, 1, 1, 0};
	P[0] = t;
	for (i=1;i<40;i++) P[i] = P[i-1]*P[i-1];
	scanf("%lld%lld", &n, &k);
	pn.a=fibo(n), pn.b=fibo(n-1);
	pnk=exp(pn,k);
	dap.a=(pnk.a*exp(fibo(k),mod-2))%mod;
	dap.b=(pnk.b-dap.a*fibo(k-1))%mod;
	if(dap.b<0)dap.b+=mod;
	printf("%lld %lld", dap.a, dap.b);
	return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 0 / 3