Submission #18991

#	Time	Username	Problem	Language	Result	Execution time	Memory
18991		kriii	흑백 (kriii4_G)	C++14	100 / 100	319 ms	9060 KiB

G

#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;
}

• Subtask 1: 6 / 6
• Subtask 2: 94 / 94