Submission #19225

#	Time	Username	Problem	Language	Result	Execution time	Memory
19225		kriii	로봇 (kriii4_F)	C++14	100 / 100	0 ms	1084 KiB

F

#include <stdio.h>

const long long mod = 1000000007;

long long pow(long long a, long long p)
{
	a %= mod;
	p = (p % (mod - 1) + mod - 1) % (mod - 1);
	long long r = 1;
	while (p){
		if (p & 1) r = r * a % mod;
		a = a * a % mod;
		p /= 2;
	}
	return r;
}

struct complex{
	complex(){
		x = y = 0;
	}
	complex(long long x_){
		x = (x_ % mod + mod) % mod;
		y = 0;
	}
	complex(long long x_, long long y_){
		x = (x_ % mod + mod) % mod;
		y = (y_ % mod + mod) % mod;
	}
	long long x,y;

	complex operator *(complex t){
		return complex(x*t.x-y*t.y,x*t.y+y*t.x);
	}
	complex operator *(long long a){
		return complex(x*a,y*a);
	}
	complex operator +(complex t){
		return complex(x+t.x,y+t.y);
	}
	complex operator -(complex t){
		return complex(x-t.x,y-t.y);
	}
};

struct triple{
	triple(){
		a = complex();
		b = complex();
		c = complex();
	}
	triple(complex a_, complex b_, complex c_){
		a = a_;
		b = b_;
		c = c_;
	}
	complex a,b,c;
};

triple sum(complex u, long long n)
{
	triple res;
	if (n == 1){
		res = triple(u,1,0);
	}
	else if (n & 1){
		triple prv = sum(u,n-1);
		res = triple(prv.a*u,prv.b+prv.a,prv.c+prv.a*(n-1));
	}
	else{
		triple half = sum(u,n/2);
		res = triple(half.a*half.a,half.b*(half.a+1),half.c*(half.a+1)+half.b*half.a*(n/2));
	}
	return res;
}

int main()
{
	long long n,l,m,r;
	scanf ("%lld %lld %lld %lld",&n,&l,&m,&r);

	long long inv = pow(l+m+r,-1);
	complex u(m,l-r),v(m,r-l);
	u = u * inv;
	v = v * inv;
	triple p = sum(u,n), q = sum(v,n);
	complex ans = (p.b + q.b) * n - p.c - q.c - n;
	if (ans.y) return 0;

	printf ("%lld\n",ans.x);

	return 0;
}

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