#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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
508 KB |
Output is correct |
| 3 |
Correct |
2 ms |
544 KB |
Output is correct |
| 4 |
Correct |
2 ms |
544 KB |
Output is correct |
| 5 |
Correct |
2 ms |
584 KB |
Output is correct |
| 6 |
Correct |
2 ms |
584 KB |
Output is correct |
| 7 |
Correct |
2 ms |
584 KB |
Output is correct |
| 8 |
Correct |
2 ms |
584 KB |
Output is correct |
| 9 |
Correct |
2 ms |
584 KB |
Output is correct |
| 10 |
Correct |
2 ms |
584 KB |
Output is correct |
| 11 |
Correct |
3 ms |
584 KB |
Output is correct |
| 12 |
Correct |
2 ms |
584 KB |
Output is correct |
| 13 |
Correct |
2 ms |
584 KB |
Output is correct |
| 14 |
Correct |
2 ms |
584 KB |
Output is correct |
| 15 |
Correct |
3 ms |
584 KB |
Output is correct |
| 16 |
Correct |
2 ms |
584 KB |
Output is correct |
| 17 |
Correct |
3 ms |
584 KB |
Output is correct |
| 18 |
Correct |
2 ms |
584 KB |
Output is correct |
| 19 |
Correct |
3 ms |
584 KB |
Output is correct |
| 20 |
Correct |
4 ms |
584 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
664 KB |
Output is correct |
| 2 |
Correct |
2 ms |
664 KB |
Output is correct |
| 3 |
Correct |
2 ms |
664 KB |
Output is correct |
| 4 |
Correct |
3 ms |
732 KB |
Output is correct |
| 5 |
Correct |
2 ms |
732 KB |
Output is correct |
| 6 |
Correct |
3 ms |
732 KB |
Output is correct |
| 7 |
Correct |
3 ms |
732 KB |
Output is correct |
| 8 |
Correct |
2 ms |
732 KB |
Output is correct |
| 9 |
Correct |
2 ms |
732 KB |
Output is correct |
| 10 |
Correct |
3 ms |
732 KB |
Output is correct |
| 11 |
Correct |
2 ms |
732 KB |
Output is correct |
| 12 |
Correct |
2 ms |
732 KB |
Output is correct |
| 13 |
Correct |
2 ms |
732 KB |
Output is correct |
| 14 |
Correct |
2 ms |
732 KB |
Output is correct |
| 15 |
Correct |
2 ms |
732 KB |
Output is correct |
| 16 |
Correct |
2 ms |
780 KB |
Output is correct |
| 17 |
Correct |
3 ms |
780 KB |
Output is correct |
| 18 |
Correct |
2 ms |
780 KB |
Output is correct |
| 19 |
Correct |
3 ms |
780 KB |
Output is correct |
| 20 |
Correct |
3 ms |
792 KB |
Output is correct |
