Submission #19979

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19979	2016-02-25T08:06:43 Z	myungwoo	로봇 (kriii4_F)	C++14	0 / 100	0 ms	16724 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)
	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] = 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=xs[i], fy=ys[i];
				if(i==0)fx+=c.xs[i], fy+=c.ys[i];
				if(i==1)fx-=c.ys[i], fy+=c.xs[i];
				if(i==2)fx-=c.xs[i], fy-=c.ys[i];
				if(i==3)fx+=c.ys[i], fy-=c.xs[i];
				fx=(fx%mod+mod)%mod, fy=(fy%mod+mod)%mod;

				res.xs[k] += fx * c.prb[j];
				res.xs[k] %= mod;
				res.ys[k] += fy * c.prb[j];
				res.ys[k] %= mod;
			}
		}
		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[0]=1, im.prb[1]=l*inv(lmr)%mod, im.prb[2]=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.xs[0]=1, im.ys[1]=1, im.ys[3]=-1;
		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.prb[i]*dap.xs[i], xs%=mod;
		ys += dap.prb[i]*dap.ys[i], ys%=mod;
	}
	printf("%lld", (xs*xs+ys*ys)%mod);
	return 0;
}

Subtask #1

0.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	16724 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	-