#include<stdio.h>
#include<memory.h>
#define mod 1000000007
#define inv(a) exp(a,mod-2)
typedef long long lld;
lld exp(lld a, lld b){
if(b==0)return 1;
lld k=exp(a, b/2);
k=(k*k)%mod;
if(b%2)k=(k*a)%mod;
return k;
}
lld fac[1001001], rfac[1001001];
void init(){
lld i;
fac[0]=rfac[0]=1;
for(i=1; i<=1000000; i++){
fac[i]=(fac[i-1]*i)%mod;
rfac[i]=inv(fac[i]);
}
}
lld comb(lld a, lld b){
return fac[a]*rfac[b]%mod*rfac[a-b]%mod;
}
struct tt {
lld prb[4], xs[4], ys[4]; // R start, final state R U L D (x^2, y^2)
lld x2s[4], y2s[4];
tt operator* (const tt& c) const {
tt res;
lld i, j;
for(i=0; i<4; i++){
res.prb[i] = res.xs[i] = res.ys[i] = res.x2s[i] = res.y2s[i] = 0;
}
for(i=0; i<4; i++){ // first robot turn
for(j=0; j<4; j++){ // second robot turn
lld k=(i+j)%4;
res.prb[k] += prb[i] * c.prb[j];
res.prb[k] %= mod;
lld fx, fy, f2x, f2y;
if(i==0){
fx = (xs[i]+c.xs[j]), fy = (ys[i]+c.ys[j]);
f2x = (x2s[i]+c.x2s[j])+2*xs[i]*c.xs[j];
f2y = (y2s[i]+c.y2s[j])+2*ys[i]*c.ys[j];
}
if(i==1){
fx = (xs[i]-c.ys[j]), fy = (ys[i]+c.xs[j]);
f2x = (x2s[i]+c.y2s[j])-2*xs[i]*c.ys[j];
f2y = (y2s[i]+c.x2s[j])+2*ys[i]*c.xs[j];
}
if(i==2){
fx = (xs[i]-c.xs[j]), fy = (ys[i]-c.ys[j]);
f2x = (x2s[i]+c.x2s[j])-2*xs[i]*c.xs[j];
f2y = (y2s[i]+c.y2s[j])-2*ys[i]*c.ys[j];
}
if(i==3){
fx = (xs[i]+c.ys[j]), fy = (ys[i]-c.xs[j]);
f2x = (x2s[i]+c.y2s[j])+2*xs[i]*c.ys[j];
f2y = (y2s[i]+c.x2s[j])-2*ys[i]*c.xs[j];
}
fx=(fx%mod+mod)%mod, fy=(fy%mod+mod)%mod;
f2x=(f2x%mod+mod)%mod, f2y=(f2y%mod+mod)%mod;
// printf("%lld: pr%lld fx%lld fy%lld f2x%lld f2y%lld\n", k, prb[i] * c.prb[j]%mod, fx, fy, f2x, f2y);
res.xs[k] += fx;
res.xs[k] %= mod;
res.ys[k] += fy;
res.ys[k] %= mod;
res.x2s[k] += f2x;
res.x2s[k] %= mod;
res.y2s[k] += f2y;
res.y2s[k] %= mod;
}
}
// puts("");
return res;
}
};
lld n, l, m, r, lmr;
tt getxy(lld n){
int i;
tt im;
if(n==0){
im.prb[0]=1, im.prb[1]=0, im.prb[2]=0, im.prb[3]=0;
for(i=0; i<4; i++)im.xs[i]=0, im.ys[i]=0;
return im;
}
if(n==1){
im.prb[2]=0, im.prb[1]=l*inv(lmr)%mod, im.prb[0]=m*inv(lmr)%mod, im.prb[3]=r*inv(lmr)%mod;
for(i=0; i<4; i++)im.xs[i]=0, im.ys[i]=0, im.x2s[i]=0, im.y2s[i]=0;
im.xs[0] = im.x2s[0] = im.prb[0];
im.ys[1] = im.y2s[1] = im.prb[1];
im.y2s[3] = im.prb[3], im.ys[3] = (mod-im.prb[3])%mod;
return im;
}
im=getxy(n/2);
im=im*im;
if(n%2)im=im*getxy(1);
return im;
}
int main(){
lld i, xs=0, ys=0;
scanf("%lld%lld%lld%lld", &n, &l, &m, &r), lmr=l+m+r;
tt dap=getxy(n);
for(i=0; i<4; i++){
xs += dap.x2s[i], xs%=mod;
ys += dap.y2s[i], ys%=mod;
}
printf("%lld", (xs+ys)%mod);
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
16728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
