이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |