Zerojudge c699：軍隊部署 2

Zerojudge c699：軍隊部署 2

題目大意：有 $X$ 個種族，$Y$ 個特性，可以在 $N$ 個士兵裡每個種族挑一個士兵，每個士兵可能會具有某些特性、不具有某些特性。現在想讓挑出的 $X$ 個士兵 $Y$ 種特性都涵蓋到，請問有幾種選法。

解法：令 $a_{i, mask}$ 為第 $i$ 個種族具有特性 $mask$ 的數量，令 $A_{i, mask} = \sum\limits_{k\subseteq mask} a_{i, k}$，代表將第 $i$ 個種族特性 $mask$ 的子集加起來。假設 $X$ 個士兵湊出 $mask$ 的方法數為 $ans_{mask}$，那設 $Sum_{mask} = \prod\limits_{0\leq i < X} A_{i, mask}$，可以知道 $Sum_{mask}$ 也會是 $\sum\limits_{k\subseteq mask} ans_{i, k}$，所以求出 $Sum_{mask}$ 後，再逆推得到 $ans_{mask}$，答案就會是 $ans_{2^Y - 1}$。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for (int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int MOD = 1e9 + 7;
const int MAX = 7;
const int SIZE = 1 << 20;

int n, x, y;
int a[MAX][SIZE];

void add (int &x, int y) {
    x += y;
    x = x >= MOD ? x - MOD : x < 0 ? x + MOD : x;
}

void solve() {
    cin >> n >> x >> y;
    while (n--) {
        int c, k = 0;
        cin >> c, c--;
        for (int i = 0; i < y; i++) {
            bool b;
            cin >> b;
            k = k << 1 | b;
        }
        a[c][k]++;
    }
    n = 1 << y;
    for (int len = 1; len < n; len <<= 1) for (int mask = 0; mask < n; mask++) {
        if (mask & len) {
            for (int i = 0; i < x; i++) {
                add (a[i][mask], a[i][mask ^ len]);
            }
        }
    }
    for (int mask = 0; mask < n; mask++) for (int i = 1; i < x; i++) {
        a[0][mask] = 1ll * a[0][mask] * a[i][mask] % MOD;
    }
    for (int len = 1; len < n; len <<= 1) for (int mask = 0; mask < n; mask++) {
        if (mask & len) {
            add (a[0][mask], -a[0][mask ^ len]);
        }
    }
    cout << a[0][n - 1] << '\n';
}

int main() {
    Waimai;
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！