Submission #21999

#	Time	Username	Problem	Language	Result	Execution time	Memory
21999		gs14004	흑백 (kriii4_G)	C++11	100 / 100	366 ms	33284 KiB

G

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;

lint ipow(lint x, lint p){
	lint ret = 1, piv = x % mod;
	while(p){
		if(p&1) ret *= piv;
		piv *= piv;
		ret %= mod;
		piv %= mod;
		p >>= 1;
	}
	return ret % mod;
}

lint pwr[2000005], ipw[2000005];
lint fact[1005], invf[1005];
int n, m;

lint ncr(int x, int y){
	if(y < 0 || x < y) return 0;
	return fact[x] * (invf[y] * invf[x-y] % mod) % mod;
}

lint solve(int n, int m){
	lint ans = 0;
	for(int i=1; i<=n; i++){
		for(int k=1; k+i<=n; k++){
			ans += (ncr(n, i) * ncr(n-i, k) % mod) * 
				((ipow(ipw[i] + 1, m) - 1) * (ipow(ipw[k] + 1, m) - 1) % mod) % mod;
		}
	}
	return ans;
}

lint solve2(){
	lint ans = 0;
	for(int i=1; i<=n; i++){
		for(int j=1; j+i<=n; j++){
			lint aux = ipow(ipw[j] + 1, m) * (ipow((ipw[i] * ipow(ipw[j] + 1, mod - 2) + 1) % mod, m) + mod - 1) % mod;
			aux -= ipow(ipw[i] + 1, m) - 1;
			aux += mod;
			aux %= mod;
			ans += (ncr(n, i) * ncr(n-i, j) % mod) * aux;
			ans %= mod;
		}
	}
	return ans;
}

int main(){
	cin >> n >> m;
	pwr[0] = ipw[0] = 1;
	for(int i=1; i<=n*m*2; i++){
		pwr[i] = pwr[i-1] * 2 % mod;
		ipw[i] = ipw[i-1] * ((mod + 1) / 2) % mod;
	}
	fact[0] = invf[0] = 1;
	for(int i=1; i<=max(n, m); i++){
		fact[i] = fact[i-1] * i % mod;
		invf[i] = ipow(fact[i], mod-2);
	}
	lint x = solve(n, m) + solve(m, n) - solve2() + mod;
	cout << x % mod;
}

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