제출 #9300

#제출 시각아이디문제언어결과실행 시간메모리
9300pichuliaPhibonacci (kriii2_P)C++98
1 / 4
0 ms1088 KiB
#include<stdio.h> #include<algorithm> using namespace std; #define M (1000000007LL) long long int n, m; struct A{ long long int p,q; A(long long int x,long long int y){p=x; q=y;} A(){p=q=0;} A friend operator +(A p, A q) { long long int pp,qq; qq = (p.q + q.q)%M; pp = (p.q + q.q)/M; pp = (pp + p.p + q.p)%M; return A(pp,qq); } A friend operator *(A p, A q) { long long int pp,qq; qq = (p.q * q.q)%M; pp = (p.q * q.q)/M; pp = (pp + p.p * q.q + p.q*q.p)%M; return A(pp,qq); } }; A fibo(long long int y) { A x[4]; A z[4]; A r[4]; z[0] = z[3] = A(0,1); z[1] = z[2] = A(0,0); x[0] = x[1] = x[2] = A(1,1); x[3] = A(); if(y<0) return A(0,1); while(y) { int i, j, k; if(y%2) { for(i=0;i<4;i++) r[i] = A(); for(i=0;i<2;i++) for(j=0;j<2;j++) for(k=0;k<2;k++) { r[i*2+j] = (r[i*2+j] + z[i*2+k]*x[k*2+j]); } for(i=0;i<4;i++) z[i] = r[i]; } for(i=0;i<4;i++) r[i] = A(); for(i=0;i<2;i++) for(j=0;j<2;j++) for(k=0;k<2;k++) { r[i*2+j] = (r[i*2+j] + x[i*2+k]*x[k*2+j]); } for(i=0;i<4;i++) x[i] = r[i]; y/=2; } return z[1]; } long long int gcd_ext(long long int a) { long long int x,y,q,s[100],t[100],i; s[0]=1;t[0]=0; s[1]=0;t[1]=1; x=M;y=a; for(i=2;y;i++) { q=x/y; s[i]=s[i-2]-q*s[i-1]; t[i]=t[i-2]-q*t[i-1]; y^=x^=y^=x%=y; } return (t[i-2]+M*M)%M; } void process(long long int y,A sp,A sq) { A x[2]; A z[2]; A r[5]; z[0] = A(0,1); z[1] = A(); x[0] = sq; x[1] = sp; while(y) { int i, j; if(y%2) { r[2] = (z[1] * x[1]); r[1] = (z[0]*x[1] + x[0]*z[1]); r[0] = (z[0] * x[0]); r[1] = (r[1]+r[2]); r[0] = (r[0]+r[2]); z[0] = r[0]; z[1] = r[1]; } r[2] = (x[1] * x[1]); r[1] = (x[0]*x[1] + x[0]*x[1]); r[0] = (x[0] * x[0]); r[1] = (r[1]+r[2]); r[0] = (r[0]+r[2]); x[0] = r[0]; x[1] = r[1]; y/=2; } A p = fibo(m); A q = fibo(m-1); if(p.q == 0 ) { long long int gg = gcd_ext(p.p); long long int ppp = (gg*z[1].p)%M; long long int qqq = (ppp*q.q)%M; qqq = (M-qqq)%M; printf("%lld %lld\n",ppp, (qqq+z[0].q)%M); return; } long long int gg = gcd_ext(p.q); long long int pp,qq; pp = 1; qq = (q.q*gg)%M; qq = (M-qq)%M; long long ppp = (z[1].q * gg)%M; long long qqq = (z[0].q + qq*z[1].q)%M; printf("%lld %lld\n",ppp,qqq); } int main() { scanf("%lld %lld",&n,&m); A p,q; p = fibo(n); q = fibo(n-1); process(m,p,q); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...