제출 #56811

#제출 시각아이디문제언어결과실행 시간메모리
56811youngyojunPhibonacci (kriii2_P)C++11
1 / 4
3 ms1124 KiB
#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; } 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...