답안 #18991

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
18991 2016-02-17T02:47:19 Z kriii 흑백 (kriii4_G) C++14
100 / 100
319 ms 9060 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;
}

long long inv2[1010],comb[1010][1010];

int main()
{
	inv2[0] = 1;
	for (int i=1;i<=1000;i++){
		inv2[i] = inv2[i-1] * 500000004 % mod;
	}

	for (int i=0;i<=1000;i++){
		comb[i][0] = comb[i][i] = 1;
		for (int j=1;j<i;j++) comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % mod;
	}

	int h,w; scanf ("%d %d",&h,&w);
	long long ans = 0;
	for (int i=1;i<=h;i++) for (int j=1;i+j<=h;j++){
		long long coeff = comb[h][i] * comb[h-i][j] % mod;
		long long cnt = (pow(inv2[i]+inv2[j]+1,w) - pow(inv2[i]+1,w) - pow(inv2[j]+1,w) + 1 + mod * 2) % mod;
		ans = (ans + coeff * cnt) % mod;
	}

	for (int k=0;k<2;k++){
		for (int i=1;i<=h;i++) for (int j=1;i+j<=h;j++){
			long long coeff = comb[h][i] * comb[h-i][j] % mod;
			long long cnt = (pow(inv2[i+j]+inv2[i]+inv2[j]+1,w) - pow(inv2[i]+inv2[j]+1,w) + mod) % mod;
			ans = (ans + coeff * cnt) % mod;
		}
		int t = h; h = w; w = t;
	}
	printf ("%lld\n",ans);

	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 9060 KB Output is correct
2 Correct 0 ms 9060 KB Output is correct
3 Correct 0 ms 9060 KB Output is correct
4 Correct 2 ms 9060 KB Output is correct
5 Correct 0 ms 9060 KB Output is correct
6 Correct 0 ms 9060 KB Output is correct
7 Correct 4 ms 9060 KB Output is correct
8 Correct 4 ms 9060 KB Output is correct
9 Correct 0 ms 9060 KB Output is correct
10 Correct 0 ms 9060 KB Output is correct
11 Correct 0 ms 9060 KB Output is correct
12 Correct 0 ms 9060 KB Output is correct
13 Correct 0 ms 9060 KB Output is correct
14 Correct 0 ms 9060 KB Output is correct
15 Correct 4 ms 9060 KB Output is correct
16 Correct 0 ms 9060 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 9060 KB Output is correct
2 Correct 47 ms 9060 KB Output is correct
3 Correct 222 ms 9060 KB Output is correct
4 Correct 144 ms 9060 KB Output is correct
5 Correct 93 ms 9060 KB Output is correct
6 Correct 80 ms 9060 KB Output is correct
7 Correct 161 ms 9060 KB Output is correct
8 Correct 9 ms 9060 KB Output is correct
9 Correct 50 ms 9060 KB Output is correct
10 Correct 178 ms 9060 KB Output is correct
11 Correct 183 ms 9060 KB Output is correct
12 Correct 161 ms 9060 KB Output is correct
13 Correct 49 ms 9060 KB Output is correct
14 Correct 226 ms 9060 KB Output is correct
15 Correct 103 ms 9060 KB Output is correct
16 Correct 93 ms 9060 KB Output is correct
17 Correct 91 ms 9060 KB Output is correct
18 Correct 97 ms 9060 KB Output is correct
19 Correct 80 ms 9060 KB Output is correct
20 Correct 29 ms 9060 KB Output is correct
21 Correct 317 ms 9060 KB Output is correct
22 Correct 314 ms 9060 KB Output is correct
23 Correct 312 ms 9060 KB Output is correct
24 Correct 319 ms 9060 KB Output is correct