yukicoder : No.1846 Good Binary Matrix

どっかで見てそう。
https://yukicoder.me/problems/no/1846

問題

H*Wの01で構成される行列を考える。
どの行も、どの列も非0要素が1つ以上あるような行列は何通りか。

解法

行について包除原理を行う。
H行中i行はすべて0であったとする。各列が非0である条件は、残り(H-i)行のどこかに1が1個以上あればよい。
よってiを総当たりし、Comb(H,i) * (-1)^i * (2^(H-i)-1)^W の和を取ればよい。

int H,W;
const ll mo=1000000007;

ll comb(ll N_, ll C_) {
	const int NUM_=2400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	ll ret=0;
	FOR(i,H+1) {
		ll a=comb(H,i);
		ll b=modpow(modpow(2,H-i)-1,W);
		if(i%2==0) {
			ret+=a*b%mo;
		}
		else {
			ret-=a*b%mo;
		}
	}
	cout<<(ret%mo+mo)%mo<<endl;
	
}

まとめ

余り難しすぎない問題が多いと、サクサク解けていいよね。