이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<stdio.h>
typedef long long ll;
const int MM = 1000000007;
struct llL{
llL(){d[0] = 0, d[1] = 0;}
llL(ll d0, ll d1){ d[0] = d0; d[1] = d1; } // d0*MM+d1
ll d[2];
llL operator+(const llL l) const{
llL ans = llL(0,0);
for(int i=0;i<2;i++){
ans.d[i] = l.d[i] + d[i];
}
ans.d[0] += ans.d[1] / MM;
ans.d[1] %= MM;
ans.d[0] %= MM;
return ans;
}
llL operator*(const llL l) const{
llL ans = llL(0,0);
ans.d[1] = d[1] * l.d[1];
ans.d[0] = d[1] * l.d[0] + d[0] * l.d[1];
ans.d[0] += ans.d[1] / MM;
ans.d[1] %= MM;
ans.d[0] %= MM;
return ans;
}
};
struct Mat{
llL d[2][2];
Mat(){ d[0][0] = d[0][1] = d[1][0] = d[1][1] = llL(); }
Mat operator*(const Mat &l)const{
Mat ans = Mat();
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
for(int k=0;k<2;k++){
ans.d[i][j] = ans.d[i][j] + d[i][k]*l.d[k][j];
}
}
}
return ans;
}
};
ll pw(ll a, ll b)
{
ll ans = 1, mul = a;
while( b > 0 ){
if( b%2 == 1) ans *= mul;
mul *= mul; b/=2;
ans %= MM; mul %= MM;
}
return ans;
}
Mat Mpw(Mat a, ll b)
{
Mat ans = Mat(), mul = a;
ans.d[0][0] = ans.d[1][1] = llL(0,1);
while( b > 0 ){
if( b%2 == 1) ans = ans* mul;
mul = mul* mul; b/=2;
}
return ans;
}
ll div(ll a){ return pw(a, MM-2); }
int main()
{
ll N, K;
scanf("%lld%lld", &N, &K);
Mat dif = Mat();
dif.d[0][0] = dif.d[0][1] = dif.d[1][0] = llL(0,1);
Mat ans = Mpw( Mpw(dif, N), K), as = Mpw(dif, K-1);
llL Fnk_1 = ans.d[0][1], Fk_1 = as.d[0][0], Fnk_2 = ans.d[1][1], Fk_2 = as.d[0][1];
ll A;
if( Fk_1.d[1] == 0 ) A = Fnk_1.d[0] * div( Fk_1.d[0] ) % MM;
else A = Fnk_1.d[1] * div(Fk_1.d[1]) % MM;
ll B = ( (Fnk_2.d[1] - Fk_2.d[1] * A % MM ) + MM) % MM;
printf("%lld %lld", A, B);
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |