#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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
256 KB |
Output is correct |
| 3 |
Correct |
5 ms |
256 KB |
Output is correct |
| 4 |
Correct |
5 ms |
376 KB |
Output is correct |
| 5 |
Correct |
5 ms |
376 KB |
Output is correct |
| 6 |
Correct |
5 ms |
376 KB |
Output is correct |
| 7 |
Correct |
5 ms |
256 KB |
Output is correct |
| 8 |
Correct |
5 ms |
256 KB |
Output is correct |
| 9 |
Correct |
5 ms |
256 KB |
Output is correct |
| 10 |
Correct |
5 ms |
256 KB |
Output is correct |
| 11 |
Correct |
5 ms |
376 KB |
Output is correct |
| 12 |
Correct |
5 ms |
256 KB |
Output is correct |
| 13 |
Correct |
5 ms |
376 KB |
Output is correct |
| 14 |
Correct |
5 ms |
256 KB |
Output is correct |
| 15 |
Correct |
5 ms |
256 KB |
Output is correct |
| 16 |
Correct |
5 ms |
256 KB |
Output is correct |
| 17 |
Correct |
5 ms |
256 KB |
Output is correct |
| 18 |
Correct |
5 ms |
256 KB |
Output is correct |
| 19 |
Correct |
5 ms |
256 KB |
Output is correct |
| 20 |
Correct |
5 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
Output is correct |
| 2 |
Correct |
5 ms |
256 KB |
Output is correct |
| 3 |
Correct |
5 ms |
376 KB |
Output is correct |
| 4 |
Correct |
5 ms |
256 KB |
Output is correct |
| 5 |
Correct |
5 ms |
376 KB |
Output is correct |
| 6 |
Correct |
5 ms |
376 KB |
Output is correct |
| 7 |
Correct |
5 ms |
376 KB |
Output is correct |
| 8 |
Correct |
5 ms |
256 KB |
Output is correct |
| 9 |
Correct |
5 ms |
256 KB |
Output is correct |
| 10 |
Correct |
5 ms |
376 KB |
Output is correct |
| 11 |
Correct |
5 ms |
256 KB |
Output is correct |
| 12 |
Correct |
5 ms |
376 KB |
Output is correct |
| 13 |
Correct |
5 ms |
256 KB |
Output is correct |
| 14 |
Correct |
5 ms |
376 KB |
Output is correct |
| 15 |
Correct |
5 ms |
256 KB |
Output is correct |
| 16 |
Correct |
5 ms |
376 KB |
Output is correct |
| 17 |
Correct |
5 ms |
256 KB |
Output is correct |
| 18 |
Correct |
5 ms |
504 KB |
Output is correct |
| 19 |
Correct |
5 ms |
376 KB |
Output is correct |
| 20 |
Correct |
4 ms |
256 KB |
Output is correct |
