JOI春合宿 2011-day2 keycards

問題文 : カードキー

解法 :
包除原理のようなものをつかう.

この問題は, "0 ~ 2 ^ (N - K)までの数から, すくなくとも1つ数をつかって論理積を0にする組み合わせの総数はいくつか", という問題に置き換えられる.

数の選び方は, U = 2 ^ (2 ^ (N - K)) - 1 通りあるので, 答えは U - (いずれかのbitが立っている組み合わせの総数)となる.
このいずれかのbitが立っている組み合わせの総数は

Σ[i = 1, N-K] (-1)^i * _{N-K}C_{i} * (2^(2^(N-K-i)) - 1)

となる. この式を計算すれば良い.
繰り返し2乗法などで計算するとO(NlogN)時間でこの式の計算ができる.

ここで, 2の冪乗やコンビネーションの計算を, 1度にO(logN)時間をかけて計算すると, 剰余演算子の計算が遅くてTLEしてしまうので, 次のような工夫を行う.

・前もってn!の逆元(=d)とnPkを求めておくと, nCk = d * nP(k+1) * nP(n-k+1) となる. 前計算にそれぞれO(N)時間かけておくことで, nCkをO(1)時間で求めることができる.

・2^(2^a) = 2^(2^(a-1)) * 2^(2^(a-1)) となるので, O(N)時間で前計算をしておくことでO(1)時間で2^(2^a)の値を求めることができる.

以上の工夫を行うことで, 上の式をO(N)時間で求めることができる.

コード :

#include <cstdio>

#define MOD (1000000007)

typedef long long ll;

using namespace std;

ll perm[1000001];
ll bper[1000002];
ll pow2[1000001];
void init(ll lim)
{
	ll i;
	perm[0] = bper[lim + 1] = 1;
	for (i = 1; i <= lim; i++){
		perm[i] = (i * perm[i - 1]) % MOD;
		bper[lim - i + 1] = (lim - i + 1) * bper[lim - i + 2] % MOD;
	}
	bper[0] = bper[1];
}

ll modPow(ll a, ll k, ll m)
{
	ll r = 1ll;
	ll t = a;
	while (k){
		if (k & 1){
			r *= t;
			r %= m;
		}
		t *= t;
		t %= m;
		k >>= 1;
	}
	return (r);
}

int main()
{
	int N, K;
	ll deno, comb;
	scanf("%d %d", &N, &K);
	
	pow2[0] = 2;
	for (int i = 1; i <= N - K; i++){
		pow2[i] = (pow2[i - 1] * pow2[i - 1]) % MOD;
	}

	ll res = pow2[N - K] - 1;
	init(N - K);
	deno = modPow(perm[N - K], MOD - 2, MOD);
	for (int i = 1; i <= N - K; i++){
		comb = deno * bper[i + 1] % MOD * bper[N - K - i + 1] % MOD;
		ll t = comb * (pow2[N - K - i] - 1) % MOD;
		if (i & 1){
			res = (res - t + MOD) % MOD;
		}
		else {
			res = (res + t) % MOD;
		}
	}
	init(N);
	deno = modPow(perm[N], MOD - 2, MOD);
	comb = deno % MOD * bper[K + 1] % MOD * bper[N - K + 1] % MOD;
	res = res * comb % MOD;
	
	printf("%lld\n", res);
	
	return (0);
}