| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 9281 |
2014-09-28T05:20:37 Z |
myungwoo |
Phibonacci (kriii2_P) |
C++14 |
|
0 ms |
1088 KB |
#include<stdio.h>
#define mod 1000000007
typedef long long lld;
struct term {
lld a, b;
term operator* (const term& c){
term k;
k.a = a*c.b+b*c.a, k.b = b*c.b;
k.a += a*c.a, k.b += a*c.a;
return k;
}
term operator% (const lld c){
term k;
k.a%=c, k.b%=c;
return k;
}
}pn, pnk, dap;
struct MAT{
lld m[2][2];
MAT operator * (const MAT &ot)const{
MAT ret={0, };
int i, j, k;
for (i=0;i<2;i++) for (j=0;j<2;j++) for (k=0;k<2;k++)
ret.m[i][j] = (ret.m[i][j]+(lld)m[i][k]*ot.m[k][j]%mod)%mod;
return ret;
}
} P[40];
lld n, k;
template <class T>
T exp(T a, lld b){
if(b==1)return a;
T im=exp(a,b/2);
im=im*im, im=im%mod;
if(b%2)im=im*a, im=im%mod;
return im;
}
lld fibo(lld n){
MAT t ={1, 0, 0, 1};
if(n<0)return 1;
int i;
for (i=0;i<40;i++) if ((n>>i)&1) t = t*P[i];
return t.m[0][1];
}
int main(){
lld i;
MAT t ={1, 1, 1, 0};
P[0] = t;
for (i=1;i<40;i++) P[i] = P[i-1]*P[i-1];
scanf("%lld%lld", &n, &k);
pn.a=fibo(n), pn.b=fibo(n-1);
pnk=exp(pn,k);
dap.a=(pnk.a*exp(fibo(k),mod-2))%mod;
dap.b=(pnk.b-dap.a*fibo(k-1))%mod;
if(dap.b<0)dap.b+=mod;
printf("%lld %lld", dap.a, dap.b);
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 |
Incorrect |
0 ms |
1088 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
