답안 #20075

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
20075	2016-02-25T09:41:09 Z	gs13068	로봇 (kriii4_F)	C++	4 / 100	40 ms	524288 KB

F

#include <cstdio>
#include <map>

const int p = 1000000007;

using namespace std;

int f(int x, int y)
{
	return y & 1 ? (long long)f(x, y ^ 1)*x%p : y ? f((long long)x*x%p, y >> 1) : 1;
}

map<pair<int, pair<pair<int, int>, int> >, int> MM;

int px[4] = { 1,0,-1,0 };
int py[4] = { 0,1,0,-1 };

int L, R, M;

int g(int n, int x, int y, int z)
{
	if (n == 0) return x*x + y*y;
	if (MM.find(make_pair(n, make_pair(make_pair(x, y), z))) != MM.end()) return MM[make_pair(n, make_pair(make_pair(x, y), z))];
	int a = (long long)g(n - 1, x + px[z], y + py[z], z) * M % p;
	z = z + 1 & 3;
	int b = (long long)g(n - 1, x + px[z], y + py[z], z) * L % p;
	z = z + 2 & 3;
	int c = (long long)g(n - 1, x + px[z], y + py[z], z) * R % p;
	return MM[make_pair(n, make_pair(make_pair(x, y), z + 1 & 3))] = ((long long)a + b + c) * f(L + R + M, p - 2) % p;
}

int main()
{
	int n;
	scanf("%d%d%d%d", &n, &L, &M, &R);
	printf("%d", g(n, 0, 0, 0));
}

Subtask #1

4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1212 KB	Output is correct
2	Correct	0 ms	1212 KB	Output is correct
3	Correct	0 ms	1212 KB	Output is correct
4	Correct	2 ms	1212 KB	Output is correct
5	Correct	0 ms	1212 KB	Output is correct
6	Correct	0 ms	1212 KB	Output is correct
7	Correct	2 ms	1212 KB	Output is correct
8	Correct	0 ms	1212 KB	Output is correct
9	Correct	0 ms	1212 KB	Output is correct
10	Correct	3 ms	1344 KB	Output is correct
11	Correct	0 ms	1212 KB	Output is correct
12	Correct	0 ms	1212 KB	Output is correct
13	Correct	0 ms	1212 KB	Output is correct
14	Correct	0 ms	1212 KB	Output is correct
15	Correct	0 ms	1212 KB	Output is correct
16	Correct	2 ms	1212 KB	Output is correct
17	Correct	0 ms	1212 KB	Output is correct
18	Correct	0 ms	1212 KB	Output is correct
19	Correct	0 ms	1212 KB	Output is correct
20	Correct	0 ms	1212 KB	Output is correct
21	Correct	0 ms	1212 KB	Output is correct
22	Correct	0 ms	1212 KB	Output is correct
23	Correct	0 ms	1212 KB	Output is correct
24	Correct	0 ms	1212 KB	Output is correct
25	Correct	0 ms	1212 KB	Output is correct
26	Correct	0 ms	1212 KB	Output is correct
27	Correct	0 ms	1212 KB	Output is correct
28	Correct	2 ms	1212 KB	Output is correct
29	Correct	3 ms	1344 KB	Output is correct
30	Correct	4 ms	1344 KB	Output is correct

Subtask #2

0.0 / 96.0

#	결과	실행 시간	메모리	Grader output
1	Memory limit exceeded	40 ms	524288 KB	Memory limit exceeded
2	Halted	0 ms	0 KB	-