Submission #20060

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
20060	2016-02-25T08:58:26 Z	xdoju	로봇 (kriii4_F)	C++14	0 / 100	1000 ms	1720 KB

F

#include <iostream>
#include <cstdio>

using namespace std;
typedef long long ll;

const int MOD = 1000000007ll;

inline int modpow(int r, int n) {
	int ret = 1;
	while (n > 0) {
		if (n % 2 > 0) {
			ret = ((long long)ret * r) % MOD;
		}
		r = ((long long)r * r) % MOD;
		n /= 2;
	}
	return ret;
}

inline int modinv(int n) {
	return modpow(n, MOD - 2);
}

inline int modprod(int a, int b) {
	a = a % MOD;
	b = b % MOD;
	return ((long long)a * b) % MOD;
}

inline int modprod(int a, int b, int c) {
	c = c % MOD;
	return (modprod(a, b) * (long long)c) % MOD;
}

inline int moddiv(int a, int b) {
	return ((long long)a * modinv(b)) % MOD;
}

int n, l, m, r;
int ans = 0;
int a[22];

int brute2() {
	int p = 1, x = 0, y = 0, dir = 0;

	for (int i = 0; i < n; i++) {
		if (a[i] == 0)
			p = modprod(p, l);
		else if (a[i] == 1)
			p = modprod(p, m);
		else
			p = modprod(p, r);

		if (dir == 0) {
			if (a[i] == 0) y = y + 1, dir = 1;
			else if (a[i] == 1) x = x + 1, dir = 0;
			else y = y - 1, dir = 3;
		}
		else if (dir == 1) {
			if (a[i] == 0) x = x - 1, dir = 2;
			else if (a[i] == 1) y = y + 1, dir = 1;
			else x = x + 1, dir = 0;
		}
		else if (dir == 2) {
			if (a[i] == 0) y = y - 1, dir = 3;
			else if (a[i] == 1) x = x - 1, dir = 2;
			else y = y + 1, dir = 1;
		}
		else {
			if (a[i] == 0) x = x + 1, dir = 0;
			else if (a[i] == 1) y = y - 1, dir = 3;
			else x = x - 1, dir = 2;
		}
	}

	return modprod(p, modprod(x, x) + modprod(y, y));
}

void brute(int process = 0) {
	if (process == n) {
		ans += brute2();
		ans %= MOD;
		return;
	}

	a[process] = 0;
	brute(process + 1);
	a[process] = 1;
	brute(process + 1);
	a[process] = 2;
	brute(process + 1);
}

int main() {
	cin >> n >> l >> m >> r;

	brute();
	ans = modprod(ans, modinv(modpow(l + m + r, n)));
	printf("%d\n", ans);

	return 0;
}	

Subtask #1

0.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	1720 KB	Output is correct
2	Correct	0 ms	1720 KB	Output is correct
3	Correct	0 ms	1720 KB	Output is correct
4	Correct	95 ms	1720 KB	Output is correct
5	Correct	0 ms	1720 KB	Output is correct
6	Correct	0 ms	1720 KB	Output is correct
7	Correct	97 ms	1720 KB	Output is correct
8	Correct	0 ms	1720 KB	Output is correct
9	Correct	0 ms	1720 KB	Output is correct
10	Correct	304 ms	1720 KB	Output is correct
11	Correct	0 ms	1720 KB	Output is correct
12	Correct	0 ms	1720 KB	Output is correct
13	Correct	92 ms	1720 KB	Output is correct
14	Correct	0 ms	1720 KB	Output is correct
15	Correct	0 ms	1720 KB	Output is correct
16	Correct	95 ms	1720 KB	Output is correct
17	Correct	0 ms	1720 KB	Output is correct
18	Correct	0 ms	1720 KB	Output is correct
19	Correct	9 ms	1720 KB	Output is correct
20	Correct	0 ms	1720 KB	Output is correct
21	Correct	0 ms	1720 KB	Output is correct
22	Correct	0 ms	1720 KB	Output is correct
23	Correct	1 ms	1720 KB	Output is correct
24	Correct	0 ms	1720 KB	Output is correct
25	Correct	30 ms	1720 KB	Output is correct
26	Correct	0 ms	1720 KB	Output is correct
27	Correct	0 ms	1720 KB	Output is correct
28	Correct	30 ms	1720 KB	Output is correct
29	Correct	973 ms	1720 KB	Output is correct
30	Execution timed out	1000 ms	1716 KB	Program timed out

Subtask #2

0.0 / 96.0

#	Verdict	Execution time	Memory	Grader output
1	Halted	0 ms	0 KB	-