Submission #56824

#	Time	Username	Problem	Language	Result	Execution time	Memory
56824		youngyojun	Phibonacci (kriii2_P)	C++11	4 / 4	4 ms	792 KiB

P

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll MOD = 1000000007;

void add(ll &a, ll b) { a = ((a+b) % MOD + MOD) % MOD; }

struct MAT {
	MAT() { d[0][0] = d[0][1] = d[1][0] = d[1][1] = 0; }
	ll d[2][2];

	MAT operator * (const MAT t) const {
		MAT ret;
		for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++) for(int k = 0; k < 2; k++)
			add(ret.d[i][j], d[i][k] * t.d[k][j]);
		return ret;
	}
};

ll pw(ll n, ll k) {
	ll ret = 1;
	for(; k; k >>= 1) {
		if(k&1) ret = ret*n % MOD;
		n = n*n % MOD;
	}
	ret = (ret + MOD) % MOD;
	return ret;
}

ll inv(ll n) { return pw(n, MOD-2); }

MAT pw(MAT t, ll n) {
	MAT ret;
	ret.d[0][0] = ret.d[1][1] = 1;
	for(; n; n >>= 1) {
		if(n&1) ret = ret * t;
		t = t*t;
	}
	return ret;
}

ll phi(ll n, ll m = 1, bool sex = false) {
	MAT key;
	key.d[0][0] = key.d[0][1] = key.d[1][0] = 1;
	key = pw(key, n);
	key = pw(key, m);
	if(sex) {
		MAT rev;
		rev.d[0][1] = rev.d[1][0] = 1;
		rev.d[1][1] = MOD-1;
		key = key * rev;
	}
	return key.d[1][0];
}

ll N, K, A, B;

int main() {
	cin >> N >> K;

	A = phi(N, K) * inv(phi(K)) % MOD;
	if(!phi(K)) A = pw(phi(K-1), N-1) * N % MOD;
	B = (phi(N, K, true) - A * phi(K, 1, true)) % MOD;
	A = (A + MOD) % MOD;
	B = (B + MOD) % MOD;

	cout << A << " " << B << endl;
	return 0;
}

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