Submission #19285

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19285	2016-02-24T05:00:04 Z	kaTkaHr	로봇 (kriii4_F)	C++14	4 / 100	1000 ms	16868 KB

F

#include <stdio.h>
#include<vector>
#include <algorithm>
#include <map>

using namespace std;

typedef long long ll;

const int MX = 1005, MM = 1000000007;

ll pw(ll A, ll B){
  ll R = 1;
  while(B){
    if( B&1 ) R = R * A % MM;
    A = A * A % MM; B /= 2;
  }
  return R;
}


ll rv(ll A){ return pw(A, MM-2); }
//*
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; }
};// */

frac pw(frac A, ll B){
  frac R = 1;
  while(B){
    if( B&1 ) R = R * A;
    A = A * A; B /= 2;
  }
  return R;
}

frac CC[MX][MX];

frac C(ll A, ll B)
{
	return CC[A][B];
}

int main()
{
	CC[0][0] = 1;
	for(int i = 1; i <= 100; i++){
		CC[i][0] = 1;
		for(int j = 1; j <= i; j++) CC[i][j] = CC[i-1][j] + CC[i-1][j-1];
	}

	int N, L, M, R;
	scanf("%d%d%d%d", &N, &L, &M, &R);
	frac ans = 0;
	for(int i = 1; i < N; i++){
		for(int j = 0; j <= i; j++){
			frac res = 0;
			for(int k = 0; k+j <= i; k++){
				frac tmp = pw(frac(R, L+M+R), k) * pw(frac(M, L+M+R), i-j-k) * C(i-j, k);
				if( (j+k) %2 == 1 );
				else if( (j+3*k)%4 == 0) res = res + tmp;
				else res = res - tmp;
			}
			ans = ans + res * pw(frac(L, L+M+R), j) * C(i, j) * (N-i);
		}
	}
	ans = ans * 2 + N;
	printf("%lld\n", ans.v());
}

Subtask #1

4.0 / 4.0

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

Subtask #2

0.0 / 96.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1000 ms	16864 KB	Program timed out
2	Halted	0 ms	0 KB	-