| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 9821 |
2014-09-28T11:00:59 Z |
veckal |
Phibonacci (kriii2_P) |
C++14 |
|
0 ms |
1088 KB |
#include<cstdio>
#include<utility>
using namespace std;
typedef long long ll;
const int MOD = 1000000000 + 7;
ll n, k;
struct Matrix {
ll mat[2][2];
Matrix() {
mat[0][0]=mat[0][1]=mat[1][0]=mat[1][1]=0;
}
};
Matrix operator *(Matrix& A, Matrix& B) {
Matrix ret;
for (int i=0; i<2; ++i)
for (int j=0; j<2; ++j)
for (int k=0; k<2; ++k)
ret.mat[i][j] = (ret.mat[i][j] + A.mat[i][k] * B.mat[k][j])%MOD;
return ret;
}
Matrix power(Matrix base, ll exp) {
Matrix ret;
ret.mat[0][0] = ret.mat[1][1] = 1;
while(exp) {
if (exp&1) ret = ret * base;
base = base * base;
exp >>= 1;
}
return ret;
}
pair<long long, long long> extended_gcd(long long a, long long b) {
if (b == 0) return make_pair(1, 0);
pair<long long, long long> t = extended_gcd(b, a % b);
return make_pair(t.second, t.first - t.second * (a / b));
}
long long modinverse(long long a, long long m) {
return (extended_gcd(a, m).first % m + m) % m;
}
ll power(ll base, ll exp) {
if (exp < 0) return 0;
ll ret = 1;
while(exp) {
if (exp&1) ret = (ret*base)%MOD;
base = (base*base)%MOD;
exp >>= 1;
}
return ret;
}
int main() {
scanf("%lld%lld", &n, &k);
Matrix base;
base.mat[0][0] = base.mat[0][1] = base.mat[1][0] = 1;
Matrix a_k = power(base, k);
Matrix a_nk = power(a_k, n);
ll f_nk = a_nk.mat[0][1];
ll f_nk_1 = a_nk.mat[1][1];
ll f_k = a_k.mat[0][1];
ll f_k_1 = a_k.mat[1][1];
ll ans1, ans2;
if (f_k == 0) ans1 = n * power(f_k_1, n-1) % MOD;
else ans1 = f_nk * modinverse(f_k, MOD) % MOD;
ans2 = (f_nk_1 - f_k_1 * ans1 % MOD + MOD) % MOD;
printf("%lld %lld\n", ans1, ans2);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 11 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 12 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 13 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 14 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 15 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 16 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 17 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 18 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 19 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 20 |
Correct |
0 ms |
1088 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 11 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 12 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 13 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 14 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 15 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 16 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 17 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 18 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 19 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 20 |
Correct |
0 ms |
1088 KB |
Output is correct |
