oj.uz

Submission #19289

# Submission time Handle Problem Language Result Execution time Memory
19289 2016-02-24T06:11:50 Z kaTkaHr 로봇 (kriii4_F) C++14
100 / 100
 0 ms 1092 KB 
#include <stdio.h>
#include<vector>
#include <algorithm>
#include <map>

using namespace std;

typedef long long ll;

const int MX = 1005, MM = 1000000007;

template<typename T>
T pw(T A, ll B){
  T R = 1;
  while(B){
    if( B&1 ) R = R * A;
    A = A * A; B /= 2;
  }
  return R;
}

ll rv(ll A){ 
  ll R = 1, B = MM-2;
  while(B){
    if( B&1 ) R = R * A % MM;
    A = A * A % MM; B /= 2;
  }
  return R;
}
//*
struct frac{
  ll A, B;
		frac(ll A):A(A), B(1){}
  frac(ll a, ll b){
    A = (a%MM+MM) % MM;
    B = (b%MM+MM) % MM;
  }
  frac(){A = 0, B = 1;}
  frac operator+ (const frac &l)const{
    return frac((A * l.B + B * l.A) % MM, B * l.B % MM);
  }
  frac operator*(const frac &l)const{
    return frac(A*l.A % MM, B*l.B % MM);
  }
  frac operator/(const frac &l)const{
    return frac(A*l.B % MM, B*l.A % MM);
  }
  frac operator- (const frac &l)const{
    return frac((A*l.B - B*l.A%MM + MM) % MM, B*l.B % MM);
  }
  ll v(){ return A * rv(B) % MM; }
};// */
/*
struct frac{
  ll A;
		frac(ll A):A((A%MM+MM)%MM){}
  frac(ll a, ll b){
			a = (a%MM+MM)%MM;
			b = (b%MM+MM)%MM;
			A = rv(b) * a % MM;
  }
  frac(){A = 0;}
  frac operator+ (const frac &l)const{
			return l.A + A >= MM? l.A + A - MM: l.A + A;
  }
  frac operator*(const frac &l)const{
			return l.A * A % MM;
  }
  frac operator/(const frac &l)const{
			return A * rv(l.A) % MM;
  }
  frac operator- (const frac &l)const{
			return A >= l.A? A-l.A: A-l.A + MM;
  }
  ll v(){ return A; }
};// */

struct Complex{
	frac R, I;
	Complex(frac R, frac I):R(R), I(I){}
	Complex(frac R):R(R), I(0){}
	Complex(ll R):R(R), I(0){}

	frac norm()const{ return R*R + I*I; }
	
	Complex operator+(const Complex &l)const{
		return Complex(R+l.R, I+l.I);
	}
	
	Complex operator-(const Complex &l)const{
		return Complex(R-l.R, I-l.I);
	}

	Complex operator*(const Complex &l)const{
		return Complex(R*l.R - I*l.I, R*l.I + I*l.R);
	}
	
	Complex operator/(const Complex &l)const{
		return Complex(R, I) * Complex(l.R, frac(0, 1)-l.I) / l.norm();
	}

	Complex operator/(const frac &l)const{
		return Complex(R/l, I/l);
	}
	void print(){ printf("(%lld/%lld , %lld/%lld)", R.A, R.B, I.A, I.B); } 
};

int main()
{
	int N, L, M, R, T;
	scanf("%d%d%d%d", &N, &L, &M, &R); T = L + M + R;
	Complex K = Complex(frac(M, T), frac(R, T) - frac(L, T));
	if( L == 0 && R == 0){
		return !printf("%lld\n", (frac(N) * frac(N)).v());
	}
	Complex ans = (K*N - K*K*N - K + pw(K, N+1)) / (Complex(1)-K) / (Complex(1)-K);

	ans = ans * 2 + N;

	printf("%lld\n", ans.R.v());
}

Subtask #1
4.0 / 4.0

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

Subtask #2
96.0 / 96.0

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