| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 9365 |
2014-09-28T05:56:50 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;
}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;
term exp(term a, lld b){
if(b==1)return a;
term im=exp(a,b/2), im2;
im2.a=(2*im.a*im.b+im.a*im.a)%mod, im2.b=(im.b*im.b+im.a*im.a)%mod, im=im2;
if(b%2){
im2.a=(im.a*a.b+a.a*im.b+a.a*im.a)%mod, im2.b=(im.b*a.b+im.a*a.a)%mod;
im=im2;
}
return im;
}
lld exp2(lld a, lld b){
if(b==1)return a;
lld im=exp2(a,b/2);
im*=im, im%=mod;
if(b%2)im*=a, 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*exp2(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 |
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 |
Incorrect |
0 ms |
1088 KB |
Output isn't correct |
| 20 |
Halted |
0 ms |
0 KB |
- |
