Submission #9365

#	Time	Username	Problem	Language	Result	Execution time	Memory
9365		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;
}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;

term exp(term a, lld b){
	if(b==1)return a;
	term im=exp(a,b/2), im2;
	im2.a=(2*im.a*im.b+im.a*im.a)%mod, im2.b=(im.b*im.b+im.a*im.a)%mod, im=im2;
	if(b%2){
		im2.a=(im.a*a.b+a.a*im.b+a.a*im.a)%mod, im2.b=(im.b*a.b+im.a*a.a)%mod;
		im=im2;
	}
	return im;
}

lld exp2(lld a, lld b){
	if(b==1)return a;
	lld im=exp2(a,b/2);
	im*=im, im%=mod;
	if(b%2)im*=a, im%=mod;
	return im;
}

lld fibo(lld n){
	MAT t ={1, 0, 0, 1};
	if(n<0)return 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*exp2(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