| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 20034 | hongjun7 | 로봇 (kriii4_F) | C++98 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<stdio.h>
#include<algorithm>
using namespace std;
#define M 1000000007
#define N 33
long long int gcd(long long int x, long long int y)
{
x = std::abs(x);
y = std::abs(y);
if(y==0)return x;
while(x%y)
{
long long int z = x%y;
x=y;
y=z;
}
return y;
}
class B{
public:
long long int p, q;
B(){p=0;q=1;}
B(long long int x){p=x%M;q=1;gg();}
B(long long int x, long long int y){p=x%M;q=y%M;gg();}
void gg()
{
if(q<0){q = M+q;}
if(p<0){p = M+p;}
}
B operator +(B &a){
B r = B(p*a.q + q*a.p, q*a.q);
return r;
}
void operator +=(B &a){
B r = B(p*a.q + q*a.p, q*a.q);
p=r.p;
q=r.q;
}
B operator +(long long int a){
B r = B(p + q*a, q);
return r;
}
B operator -(B &a){
B r = B(p*a.q - q*a.p, q*a.q);
return r;
}
B operator *(B &a){
B r = B(p*a.p, q*a.q);
return r;
}
B operator *(long long int a){
B r = B(p*a, q);
return r;
}
B operator /(B &a){
B r = B(p*a.q, q*a.p);
return r;
}
};
class A{
public:
B a[N][N];
A(){for(int i=0;i<N;i++)for(int j=0; j<N; j++) a[i][j] = 0;}
void iden(){
for(int i=0;i<N;i++)for(int j=0; j<N; j++) a[i][j] = 0;
for(int i=0;i<N;i++)a[i][i] = 1;
}
A operator *(A &p)
{
A r;
int i, j, k;
for(i=0; i<N; i++)
{
for(j=0;j<N;j++)
{
r.a[i][j] = 0;
for(k=0; k<N; k++)
{
r.a[i][j] += (a[i][k] * p.a[k][j]);
}
}
}
return r;
}
A operator -(A &p)
{
A r;
int i, j, k;
for(i=0; i<N; i++)
{
for(j=0;j<N;j++)
{
r.a[i][j] = a[i][j] - p.a[i][j];
}
}
return r;
}
A operator +(A &p)
{
A r;
int i, j, k;
for(i=0; i<N; i++)
{
for(j=0;j<N;j++)
{
r.a[i][j] = a[i][j] + p.a[i][j];
}
}
return r;
}
void print()
{
for(int i=0; i<N; i++,printf("\n"))
for(int j=0; j<N; j++)
printf("%lld/%lld ",a[i][j].p, a[i][j].q);
}
};
long long int gcd_ext(long long int a,long long int m)
{
long long int x,y,q,s[100],t[100],i,z;
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];
z=x%y;
x=y;
y=z;
}
return (t[i-2]+m+m)%m;
}
A exxp(A a,int n)
{
A r,z;
int i, j, k;
r.iden();
z = a;
while(n)
{
if(n%2)
{
r = r*z;
}
z = z*z;
n/=2;
}
return r;
}
int main() {
int i, j, k, l;
long long int n,ll,mm,rr;
scanf("%lld %lld %lld %lld",&n,&ll,&mm,&rr);
B p,q,r;
p = B(ll, mm+ll+rr);
q = B(mm, mm+ll+rr);
r = B(rr, mm+ll+rr);
A me;
// a b c d S T 6
// aa ab ac ad bb bc bd cc cd dd 16
// aS bS cS dS aT bT cT bT 8
// E F G 3
// a b c d
me.a[0][0] = me.a[1][1] = me.a[2][2] = me.a[3][3] = q;
me.a[1][0] = me.a[2][1] = me.a[3][2] = me.a[0][3] = p;
me.a[3][0] = me.a[0][1] = me.a[1][2] = me.a[2][3] = r;
// S T
me.a[4][4] = 1;
me.a[4][0] = 1; me.a[4][2] = -1;
me.a[5][5] = 1;
me.a[5][1] = 1; me.a[5][3] = -1;
// aa ab ac ad
for(i=0;i<4;i++)
{
for(j=i;j<4;j++)
{
int id1, id2;
if(i<j)
id1 = i*4+j+6;
else
id1 = j*4+i+6;
for(k=0; k<4; k++)
{
for(l=0; l<4; l++)
{
if(k<l)
id2 = k*4+l+6;
else
id2 = l*4+k+6;
me.a[id1][id2] += me.a[j][l] * me.a[i][k];
}
}
}
}
//aS bS cS dS
for(i=0;i<4;i++)
{
for(j=0;j<4;j++)
{
me.a[i+22][j+22] = me.a[i][j];
}
for(j=0;j<4;j++)
{
int id;
if(0<j)
id = 0*4 + j + 6;
else
id = j*4 + 0 + 6;
me.a[i+22][id] += me.a[i][j];
}
for(j=0;j<4;j++)
{
int id;
if(2<j)
id = 2*4 + j + 6;
else
id = j*4 + 2 + 6;
me.a[i+22][id] += (me.a[i][j] * (-1));
}
}
//aT bT cT dT
for(i=0;i<4;i++)
{
for(j=0;j<4;j++)
{
me.a[i+26][j+26] = me.a[i][j];
}
for(j=0;j<4;j++)
{
int id;
if(1<j)
id = 1*4 + j + 6;
else
id = j*4 + 1 + 6;
me.a[i+26][id] += me.a[i][j];
}
for(j=0;j<4;j++)
{
int id;
if(3<j)
id = 3*4 + j + 6;
else
id = j*4 + 3 + 6;
me.a[i+26][id] += (me.a[i][j] * (-1));
}
}
// E
me.a[30][30] = 1;
me.a[30][22] = 2;
me.a[30][24] = -2;
me.a[30][0] = 1;
me.a[30][2] = 1;
//F
me.a[31][31] = 1;
me.a[31][27] = 2;
me.a[31][29] = -2;
me.a[31][1] = 1;
me.a[31][3] = 1;
//G
me.a[32][30] = 1;
me.a[32][31] = 1;
int ii=n;
int jj = 32;
//for(ii=0; ii<=n; ii++)
{
A rrr = exxp(me,ii+1);
{
B res = ((rrr.a[jj][0]) * q) +((rrr.a[jj][1]) * p) + ((rrr.a[jj][3]) * r)
+ ((rrr.a[jj][6])*q*q) + ((rrr.a[jj][7])*q*p) + ((rrr.a[jj][9])*q*r)
+ ((rrr.a[jj][11])*p*p) + ((rrr.a[jj][13])*p*r) + ((rrr.a[jj][21])*r*r)
;
//res = rrr.a[32][0] + rrr.a[32][6];
//printf("%lld / %lld\n",res.p, res.q);
long long int zz = gcd_ext(res.q, M);
long long int zzz = (zz * res.p)%M;
printf("%lld\n",zzz);
}
}
}