oj.uz

Submission #19225

# Submission time Handle Problem Language Result Execution time Memory
19225 2016-02-21T11:44:44 Z kriii 로봇 (kriii4_F) C++14
100 / 100
 0 ms 1084 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1084 KB Output is correct
2 Correct 0 ms 1084 KB Output is correct
3 Correct 0 ms 1084 KB Output is correct
4 Correct 0 ms 1084 KB Output is correct
5 Correct 0 ms 1084 KB Output is correct
6 Correct 0 ms 1084 KB Output is correct
7 Correct 0 ms 1084 KB Output is correct
8 Correct 0 ms 1084 KB Output is correct
9 Correct 0 ms 1084 KB Output is correct
10 Correct 0 ms 1084 KB Output is correct
11 Correct 0 ms 1084 KB Output is correct
12 Correct 0 ms 1084 KB Output is correct
13 Correct 0 ms 1084 KB Output is correct
14 Correct 0 ms 1084 KB Output is correct
15 Correct 0 ms 1084 KB Output is correct
16 Correct 0 ms 1084 KB Output is correct
17 Correct 0 ms 1084 KB Output is correct
18 Correct 0 ms 1084 KB Output is correct
19 Correct 0 ms 1084 KB Output is correct
20 Correct 0 ms 1084 KB Output is correct
21 Correct 0 ms 1084 KB Output is correct
22 Correct 0 ms 1084 KB Output is correct
23 Correct 0 ms 1084 KB Output is correct
24 Correct 0 ms 1084 KB Output is correct
25 Correct 0 ms 1084 KB Output is correct
26 Correct 0 ms 1084 KB Output is correct
27 Correct 0 ms 1084 KB Output is correct
28 Correct 0 ms 1084 KB Output is correct
29 Correct 0 ms 1084 KB Output is correct
30 Correct 0 ms 1084 KB Output is correct

Subtask #2
96.0 / 96.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1084 KB Output is correct
2 Correct 0 ms 1084 KB Output is correct
3 Correct 0 ms 1084 KB Output is correct
4 Correct 0 ms 1084 KB Output is correct
5 Correct 0 ms 1084 KB Output is correct
6 Correct 0 ms 1084 KB Output is correct
7 Correct 0 ms 1084 KB Output is correct
8 Correct 0 ms 1084 KB Output is correct
9 Correct 0 ms 1084 KB Output is correct
10 Correct 0 ms 1084 KB Output is correct
11 Correct 0 ms 1084 KB Output is correct
12 Correct 0 ms 1084 KB Output is correct
13 Correct 0 ms 1084 KB Output is correct
14 Correct 0 ms 1084 KB Output is correct
15 Correct 0 ms 1084 KB Output is correct
16 Correct 0 ms 1084 KB Output is correct
17 Correct 0 ms 1084 KB Output is correct
18 Correct 0 ms 1084 KB Output is correct
19 Correct 0 ms 1084 KB Output is correct
20 Correct 0 ms 1084 KB Output is correct
21 Correct 0 ms 1084 KB Output is correct
22 Correct 0 ms 1084 KB Output is correct
23 Correct 0 ms 1084 KB Output is correct
24 Correct 0 ms 1084 KB Output is correct
25 Correct 0 ms 1084 KB Output is correct
26 Correct 0 ms 1084 KB Output is correct
27 Correct 0 ms 1084 KB Output is correct
28 Correct 0 ms 1084 KB Output is correct
29 Correct 0 ms 1084 KB Output is correct
30 Correct 0 ms 1084 KB Output is correct