ビット列列挙は、組み合わせ問題を効率的に解決するための強力な手法です。具体的な応用例を通じてその実装方法を解説します。

問題1: ビットマスクとPopcountの総和

与えられた非負整数NとMについて、0からNまでの全ての整数iにおける (i & M) のビットカウント（popcount）の総和を求める。解法では加算処理を乗算に変換して効率化する。

例: N=22 (2進数:10110) の場合、Mの第3ビットが1ならば、ビット列を上位部と下位部に分割し、各セグメントの範囲を独立に計算する。

#include <iostream>
using namespace std;
typedef long long ll;
const ll MOD = 998244353;

int main() {
    ll total = 0, num, mask_val;
    cin >> num >> mask_val;
    
    for (int idx = 0; idx < 60; idx++) {
        if ((mask_val >> idx) & 1) {
            ll segment_mask = (1LL << idx) - 1;
            if ((num >> idx) & 1) {
                ll combined = ((num >> (idx + 1)) << idx) | (num & segment_mask);
                total = (total + combined + 1) % MOD;
            } else {
                ll adjusted = (num - (1LL << idx)) | segment_mask;
                ll combined = ((adjusted >> (idx + 1)) << idx) | (adjusted & segment_mask);
                total = (total + combined + 1) % MOD;
            }
        }
    }
    cout << total;
}

問題2: 鍵の組み合わせ検証

n本の鍵とm回のテストが与えられ、少なくともk本の正解鍵でドアが開く条件を満たす正解鍵の組み合わせ数を求める。各テストは使用鍵ビットマスクと期待結果（開く'o' or 開かない）で定義される。

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

int count_bits(int x) {
    int cnt = 0;
    while (x) {
        cnt += x & 1;
        x >>= 1;
    }
    return cnt;
}

int main() {
    int key_num, test_num, min_keys;
    cin >> key_num >> test_num >> min_keys;
    vector<int> test_masks(test_num);
    vector<char> expected(test_num);
    
    for (int i = 0; i < test_num; i++) {
        int count;
        cin >> count;
        while (count--) {
            int key_id;
            cin >> key_id;
            test_masks[i] |= (1 << (key_id - 1));
        }
        cin >> expected[i];
    }
    
    int valid_combinations = 0;
    for (int comb = 0; comb < (1 << key_num); comb++) {
        bool valid = true;
        for (int i = 0; i < test_num; i++) {
            int active_bits = count_bits(test_masks[i] & comb);
            if ((active_bits >= min_keys && expected[i] != 'o') || 
                (active_bits < min_keys && expected[i] == 'o')) {
                valid = false;
                break;
            }
        }
        if (valid) valid_combinations++;
    }
    cout << valid_combinations;
}

問題3: 等比級数による数値パターン計算

整数Nが与えられた時、Nを繰り返し連結した数値（例: N=1010 → 10101010...）を生成し、その値をmod 998244353で求める。解法では等比級数の和の公式を用いる。

#include <iostream>
#include <string>
using namespace std;
typedef long long ll;
const ll MOD = 998244353;

ll mod_pow(ll base, ll exp) {
    base %= MOD;
    ll result = 1;
    while (exp > 0) {
        if (exp & 1) result = result * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
    return result;
}

ll mod_inverse(ll x) {
    return mod_pow(x, MOD - 2);
}

int main() {
    ll num;
    cin >> num;
    int digit_count = to_string(num).size();
    ll base_power = mod_pow(10, digit_count);
    ll numerator = num % MOD * mod_pow(base_power, num) % MOD;
    ll denominator = mod_inverse((base_power - 1 + MOD) % MOD);
    cout << numerator * denominator % MOD;
}

問題4: 最小店舗選択による味覚カバー

n軒の店舗とm種類の味覚が与えられ、各店舗が提供する味覚をビットマスクで表現する。全ての味覚をカバーする最小の店舗組み合わせ数を求める。

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

int main() {
    int shop_count, flavor_count;
    cin >> shop_count >> flavor_count;
    vector<int> shop_masks(shop_count, 0);
    
    for (int i = 0; i < shop_count; i++) {
        string flavors;
        cin >> flavors;
        for (char c : flavors) {
            shop_masks[i] = (shop_masks[i] << 1) | (c == 'o');
        }
    }
    
    int min_shops = INT_MAX;
    for (int comb = 0; comb < (1 << shop_count); comb++) {
        int covered = 0, shop_used = 0;
        for (int j = 0; j < shop_count; j++) {
            if (comb & (1 << j)) {
                covered |= shop_masks[j];
                shop_used++;
            }
        }
        if (covered == (1 << flavor_count) - 1) {
            min_shops = min(min_shops, shop_used);
        }
    }
    cout << min_shops;
}