Submission #19994

#	Time	Username	Problem	Language	Result	Execution time	Memory
19994		gs12117	로봇 (kriii4_F)	C++98	100 / 100	0 ms	1088 KiB

F

#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);
}

• Subtask 1: 4 / 4
• Subtask 2: 96 / 96