Submission #9558

#	Time	Username	Problem	Language	Result	Execution time	Memory
9558		lemonsqueeze	Phibonacci (kriii2_P)	C++98	4 / 4	0 ms	1088 KiB

P

#include<stdio.h>

typedef long long ll;
const int MM = 1000000007;

struct llL{
	llL(){d[0] = 0, d[1] = 0;}
	llL(ll d0, ll d1){ d[0] = d0; d[1] = d1; } // d0*MM+d1
	ll d[2];
	llL operator+(const llL l) const{
		llL ans = llL(0,0);
		for(int i=0;i<2;i++){
			ans.d[i] = l.d[i] + d[i];
		}
		ans.d[0] += ans.d[1] / MM;
		ans.d[1] %= MM;
		ans.d[0] %= MM;
		return ans;
	}

	llL operator*(const llL l) const{
		llL ans = llL(0,0);
		ans.d[1] = d[1] * l.d[1];
		ans.d[0] = d[1] * l.d[0] + d[0] * l.d[1];
		ans.d[0] += ans.d[1] / MM;
		ans.d[1] %= MM;
		ans.d[0] %= MM;
		return ans;
	}
};

struct Mat{
	llL d[2][2];
	Mat(){ d[0][0] = d[0][1] = d[1][0] = d[1][1] = llL(); }
	Mat operator*(const Mat &l)const{
		Mat ans = Mat();
		for(int i=0;i<2;i++){
			for(int j=0;j<2;j++){
				for(int k=0;k<2;k++){
					ans.d[i][j] = ans.d[i][j] + d[i][k]*l.d[k][j];
				}
			}
		}
		return ans;
	}
};

ll pw(ll a, ll b)
{
	ll ans = 1, mul = a;
	while( b > 0 ){
		if( b%2 == 1) ans *= mul;
		mul *= mul; b/=2;
		ans %= MM; mul %= MM;
	}
	return ans;
}

Mat Mpw(Mat a, ll b)
{
	Mat ans = Mat(), mul = a;
	ans.d[0][0] = ans.d[1][1] = llL(0,1);
	while( b > 0 ){
		if( b%2 == 1) ans = ans* mul;
		mul = mul* mul; b/=2;
	}
	return ans;
}

ll div(ll a){ return pw(a, MM-2); }


int main()
{
	ll N, K;
	scanf("%lld%lld", &N, &K);
	Mat dif = Mat();
	dif.d[0][0] = dif.d[0][1] = dif.d[1][0] = llL(0,1);
	Mat ans = Mpw( Mpw(dif, N), K), as = Mpw(dif, K-1);
	llL Fnk_1 = ans.d[0][1], Fk_1 = as.d[0][0], Fnk_2 = ans.d[1][1], Fk_2 = as.d[0][1];
	ll A;
	if( Fk_1.d[1] == 0 ) A = Fnk_1.d[0] * div( Fk_1.d[0] ) % MM;
	else A = Fnk_1.d[1] * div(Fk_1.d[1]) % MM;
	ll B = ( (Fnk_2.d[1] - Fk_2.d[1] * A % MM ) + MM) % MM;
	printf("%lld %lld", A, B);
	return 0;
}

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