| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 19994 |
2016-02-25T08:14:04 Z |
gs12117 |
로봇 (kriii4_F) |
C++ |
|
0 ms |
1088 KB |
#include<stdio.h>
int n;
int a,b,c;
int mod=1000000007;
int mpow(int x,int y){
if(y==0)return 1;
long long int r=mpow(x,y/2);
r*=r;
r%=mod;
if(y%2==1){
r*=x;
r%=mod;
}
return r;
}
long long int minv(int x){
return mpow(x,mod-2);
}
struct node{
long long int x[4];
long long int y[4];
long long int d[4];
long long int s[4];
node operator+(node z){
node res;
int i,j;
long long int prob;
long long int xd,yd,sd;
for(i=0;i<4;i++){
res.x[i]=0;
res.y[i]=0;
res.d[i]=0;
res.s[i]=0;
}
for(i=0;i<4;i++){
j=0;
prob=d[j]*z.d[i]%mod;
xd=(x[j]+z.x[i]);
xd%=mod;
yd=(y[j]+z.y[i]);
yd%=mod;
sd=(s[j]+z.s[i])+xd*xd-x[j]*x[j]-z.x[i]*z.x[i]+yd*yd-y[j]*y[j]-z.y[i]*z.y[i];
sd%=mod;
sd+=mod;
sd%=mod;
res.x[(i+j)%4]+=xd*prob%mod;
res.y[(i+j)%4]+=yd*prob%mod;
res.d[(i+j)%4]+=prob%mod;
res.s[(i+j)%4]+=sd*prob%mod;
j=1;
prob=d[j]*z.d[i]%mod;
xd=(x[j]+z.y[i]);
xd%=mod;
yd=(y[j]+mod-z.x[i]);
yd%=mod;
sd=(s[j]+z.s[i])+xd*xd-x[j]*x[j]-z.x[i]*z.x[i]+yd*yd-y[j]*y[j]-z.y[i]*z.y[i];
sd%=mod;
sd+=mod;
sd%=mod;
res.x[(i+j)%4]+=xd*prob%mod;
res.y[(i+j)%4]+=yd*prob%mod;
res.d[(i+j)%4]+=prob%mod;
res.s[(i+j)%4]+=sd*prob%mod;
j=2;
prob=d[j]*z.d[i]%mod;
xd=(x[j]+mod-z.x[i]);
xd%=mod;
yd=(y[j]+mod-z.y[i]);
yd%=mod;
sd=(s[j]+z.s[i])+xd*xd-x[j]*x[j]-z.x[i]*z.x[i]+yd*yd-y[j]*y[j]-z.y[i]*z.y[i];
sd%=mod;
sd+=mod;
sd%=mod;
res.x[(i+j)%4]+=xd*prob%mod;
res.y[(i+j)%4]+=yd*prob%mod;
res.d[(i+j)%4]+=prob%mod;
res.s[(i+j)%4]+=sd*prob%mod;
j=3;
prob=d[j]*z.d[i]%mod;
xd=(x[j]+mod-z.y[i]);
xd%=mod;
yd=(y[j]+z.x[i]);
yd%=mod;
sd=(s[j]+z.s[i])+xd*xd-x[j]*x[j]-z.x[i]*z.x[i]+yd*yd-y[j]*y[j]-z.y[i]*z.y[i];
sd%=mod;
sd+=mod;
sd%=mod;
res.x[(i+j)%4]+=xd*prob%mod;
res.y[(i+j)%4]+=yd*prob%mod;
res.d[(i+j)%4]+=prob%mod;
res.s[(i+j)%4]+=sd*prob%mod;
}
for(i=0;i<4;i++){
res.x[i]%=mod;
res.y[i]%=mod;
res.d[i]%=mod;
res.s[i]%=mod;
prob=minv(res.d[i]);
res.x[i]*=prob;
res.x[i]%=mod;
res.y[i]*=prob;
res.y[i]%=mod;
res.s[i]*=prob;
res.s[i]%=mod;
}
return res;
}
};
node p;
node find(int x){
if(x==1)return p;
node res=find(x/2);
res=res+res;
if(x%2==1)res=res+p;
return res;
}
int main(){
int i;
scanf("%d%d%d%d",&n,&a,&b,&c);
for(i=0;i<4;i++){
p.x[i]=1;
p.y[i]=0;
p.s[i]=1;
}
p.d[0]=b*minv(a+b+c)%mod;
p.d[1]=c*minv(a+b+c)%mod;
p.d[2]=0;
p.d[3]=a*minv(a+b+c)%mod;
node res=find(n);
long long int ans;
ans=res.d[0]*res.s[0];
ans+=res.d[1]*res.s[1];
ans+=res.d[2]*res.s[2];
ans+=res.d[3]*res.s[3];
ans%=mod;
printf("%lld",ans);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 11 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 12 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 13 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 14 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 15 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 16 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 17 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 18 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 19 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 20 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 21 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 22 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 23 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 24 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 25 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 26 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 27 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 28 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 29 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 30 |
Correct |
0 ms |
1088 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 11 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 12 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 13 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 14 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 15 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 16 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 17 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 18 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 19 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 20 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 21 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 22 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 23 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 24 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 25 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 26 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 27 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 28 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 29 |
Correct |
0 ms |
1088 KB |
Output is correct |
| 30 |
Correct |
0 ms |
1088 KB |
Output is correct |
