This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}
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] = -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;
B = (phi(N, K, true) - A * phi(K, 1, true)) % MOD;
B = (B + MOD) % MOD;
cout << A << " " << B << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |