Submission #9273

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

P

#include<stdio.h>

typedef long long ll;
const int MM = 1000000007;

struct Mat{
	ll d[2][2];
	Mat operator*(const Mat &l)const{
		Mat ans = {0};
		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] += d[i][k]*l.d[k][j];
					ans.d[i][j] %= MM;
				}
			}
		}
		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 = {1,0,0,1}, mul = a;
	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 = {1,1,1,0}, rev = {0,1,1,-1};
	Mat ans = Mpw( Mpw(dif, N), K), as = Mpw(dif, K-1);
	ll 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 = Fnk_1 * div(Fk_1) % MM;
	ll B = ( (Fnk_2 - Fk_2 * A % MM ) + MM) % MM;
	printf("%lld %lld", A, B);
	return 0;
}

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