Submission #203508

#	Time	Username	Problem	Language	Result	Execution time	Memory
203508		coloredrabbit	Phibonacci (kriii2_P)	C++17	4 / 4	5 ms	504 KiB

P

#include<iostream>
#include<cstring>
using namespace std;
using ll = long long;
const int LIMIT = 62, M = 1e9 + 7;
struct _mt {
	ll a, b, c, d;
	_mt() { a = b = c = d = 0; }
	_mt(ll a, ll b, ll c, ll d) : a(a), b(b), c(c), d(d) {}
	void E() { a = d = 1; }
	_mt operator*(const _mt& o) {
		return _mt{ (a * o.a + b * o.c) % M
			, (a * o.b + b * o.d) % M
			, (c * o.a + d * o.c) % M
			, (c * o.b + d * o.d) % M };
	}
}F, NK, K, E, L, Lx[LIMIT], Fk;
_mt _pow(_mt a, ll n) {
	if (n <= 1) return n % 2 ? a : E;
	_mt h = _pow(a, n >> 1);
	return h * h * (n % 2 ? a : E);
}
ll _pow(ll a, ll n) {
	if (n <= 1) return n % 2 ? a : 1;
	ll h = _pow(a, n >> 1);
	return (h * h % M) * (n % 2 ? a : 1) % M;
}

ll f_2k[LIMIT], n, k;
ll gL(ll x) { 
	if (x == 0) return 2;
	_mt fx = _pow(Fk, x - 1) * _pow(F, k - 1);
	return (fx.a + fx.b * 2LL % M) % M;
}
ll gf(ll n, ll i) {
	if (n == 1) return 1;
	if (!n) return 0;
	ll x = 1LL << i, y;
	if (n & x) {
		y = n ^ x;
		return _pow(2LL, M - 2) * (gf(y, i - 1) * gL(x) % M + gL(y) * f_2k[i] % M) % M;
	}
	else
		return gf(n, i - 1);
}

int main() {
	E.E();
	ll A, B, i, fnk, fk;	
	cin >> n >> k;
	F = _mt{ 1,1,1,0 }, L = _mt{3, 1, 1, 2};
	NK = _pow(_pow(F, n), k), K = _pow(F, k);

	fnk = NK.b, fk = K.b;
	A = fnk * _pow(fk, M - 2) % M;
	
	Fk = _pow(F, k);
	_mt Fik = _pow(F, k - 1);
	Lx[0] = Fik * L;
	f_2k[0] = 1;
	for (i = 1; i < LIMIT; i++) {
		Fik = Fik * Fik * F;
		Lx[i] = Fik * L;
		f_2k[i] = f_2k[i - 1] * Lx[i - 1].b % M;
	}
	A = gf(n, LIMIT);
	B = (NK.d - A * K.d % M + M) % M;
	cout << (long long)A << ' ' << (long long)B;
	return 0;
}

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