包除原理と聞いて

問題概要

JOI の春合宿が行われる施設の宿泊棟の部屋の鍵は，カードに穴がいくつか開いた形状をしている．穴を開ける位置の候補は N 個あり，これらのうちいくつかに穴を開けた $2^{N}$ 枚の異なる鍵が作られた．

あなたは，JOI の春合宿のための 1 枚以上 $2^{N}$ 枚以下の鍵をまとめて受け取った．穴を開ける候補の位置を合わせて鍵を重ねてみたあなたは，ちょうど K か所，受け取ったすべての鍵に穴が開いている位置があることに気づいた．

このようなことが起こるような，受け取った鍵の組み合わせは何通りあるだろうか．答えを 1 000 000 007 (素数) で割った余りを求めよ．

制約

$1 \le K \le N \le 1000000$

考えたこと

この問題の難しさは「ちょうど $K$ 箇所」という部分にある。

試しに $K = 0$ としてみると、「 $2^{N}$ 枚のカードからいくつか選ぶ方法のうち、選んだすべてのカードに穴が空いているような穴位置が存在しない」場合の数を求める問題となる。これは、包除原理に慣れていれば、包除原理の典型問題であるといえる。

今回の問題も、実はその問題に帰着して考えることができる。というのも、そのちょうど $K$ 箇所の穴を決めると（ ${}_{N}\mathrm{C}_{K}$ 通りある）、残り $N-K$ 箇所の穴については、「選んだすべてのカードに穴が空いているような穴位置が存在しない」ような場合の数を求める問題になるのだ。

よって、以降、次の問題を考えることにする。

各カードの穴を開ける位置は $N-K$ 箇所ある。

$2^{N-K}$ 枚のカードからいくつか選ぶ方法のうち、選んだすべてのカードに穴が空いているような穴位置が存在しないような場合の数を求めよ。

この答えに、 ${}_{N}\mathrm{C}_{K}$ をかけたものが最終的な答えとなる。

帰着先の問題

帰着した問題は、包除原理で解くとよいだろう。具体的には、次の値を計算する。

( $2^{N-K}$ 枚のカードからいくつかのカードを選ぶ場合の数)
－ ( $N-K$ 箇所の穴位置のうち $1$ 箇所を指定して、選んだすべてのカードについて、それらの指定した穴が開いているような場合の数)
＋ ( $N-K$ 箇所の穴位置のうち $2$ 箇所を指定して、選んだすべてのカードについて、それらの指定した穴が開いているような場合の数)
－ ( $N-K$ 箇所の穴位置のうち $3$ 箇所を指定して、選んだすべてのカードについて、それらの指定した穴が開いているような場合の数)
＋......

あとは、一般に

「 $N-K$ 箇所の穴位置のうち $i$ 箇所を指定して、選んだすべてのカードについて、それらの指定した穴が開いているような場合の数」

が求められればよい。

$i$ 箇所の穴を指定する方法： ${}_{N-K}\mathrm{C}_{i}$ 通りある
指定した穴が開いているもの $2^{N-K-i}$ 枚のカードのうち、「選ぶ」「選ばない」を選択する方法は $2^{2^{N-K-i}}$ 通りあるが、1 枚も選ばない方法は不適なので、それを除くと、 $2^{2^{N-K-i}} - 1$ 通りである

これらをかけて、最終的に

${}_{N-K}\mathrm{C}_{i} (2^{2^{N-K-i}} - 1)$

と求められる。

コード

#include <iostream>
#include <vector>
using namespace std;

const int MAX = 2100000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];
void COMinit(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < MAX; i++){
        fac[i] = fac[i-1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
        finv[i] = finv[i-1] * inv[i] % MOD;
    }
}
long long COM(int n, int k){
    if(n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD;
}

int main () {
    COMinit();
    int N, K;
    cin >> N >> K;
    long long factor = COM(N, K);
    
    if (N == K) cout << factor << endl;
    else {
        // 2 のべき乗
        vector<long long> twobeki(N+1);
        twobeki[0] = 2;
        for (int i = 0; i < N; ++i) twobeki[i + 1] = (twobeki[i] * twobeki[i]) % MOD;
    
        // i 個以上空いているところ
        long long res = 0;
        for (int i = 0; i <= N-K; ++i) {
            long long tmp = COM(N-K, i) * (twobeki[N-K-i] - 1) % MOD;
            if (i & 1) res = (res - tmp + MOD) % MOD;
            else res = (res + tmp) % MOD;
        }
        cout << res * factor % MOD << endl;
    }
}