Submission #20054

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
20054	2016-02-25T08:56:17 Z	myungwoo	로봇 (kriii4_F)	C++14	0 / 100	0 ms	16728 KB

F

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

Subtask #1

0.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	16728 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2

0.0 / 96.0

#	Verdict	Execution time	Memory	Grader output
1	Halted	0 ms	0 KB	-