250616 模拟赛 T1 题解

题意

给定一个二分图，包含 \(n_1\) 个左部点和 \(n_2\) 个右部点，以及最多 \(n_1n_2\) 条边。称一个点集 \(S\) 是合法的当且仅当存在原图的一个匹配，使得 \(S\) 中的每个点都连接了一条匹配边。

给定二分图每个点的点权 \(c_i\)，有 \(q\) 次询问，每次询问给定 \(k\)，询问合法且异或和为 \(k\) 的点集 \(S\) 的数量。

\(n_1,n_2\le 20,\ 0\le c_i< 2^20\)

题解

考虑 \(S\) 合法的一个必要条件：\(S\) 左边和右边的点分别满足霍尔定理。

记 \(S_1\) 为 \(S\) 在左边的点，\(S_2\) 为 \(S\) 在右边的点，即必须存在 \(S_1\) 向 \(V_2\)（全体右部点）的完美匹配 \(E_1\) 和 \(S_2\) 向 \(V_1\)（全体左部点）的完美匹配 \(E_2\)。

稍微手玩一下发现这个条件特别充分，于是尝试证明这一点。为了方便叙述，我们将匹配边定向，记 \(x_u\) 表示左部点 \(u\) 在右边的匹配点，\(y_v\) 同理。由于每个点的入度和出度都不超过 \(1\)，因此图中形如一些链和偶环，不难发现二者都是容易调整的。

我们只需要预处理出左边和右边满足霍尔定理的子集，异或卷积即可。

但是 \(O(3^n)\) 的预处理不能通过本题。考虑集合 \(S\)，它的任意一个子集要么是它本身，要么是 \(|S|\) 个 \(S/\{x\}\) 的一个子集。这里的枚举量是 \(O(n2^n)\) 的，可以接受。

#include<bits/stl_algobase.h>
#include<cstdio>
#include<cmath>
#include<unistd.h>
#include<ctype.h>
#include<string>
#include<cassert>
#define ll long long
using namespace std;
const int N = 20;
const int MOD = 1e9 + 7;

struct istream {
    char ch;
    template<typename _Tp>
    inline istream &operator>>(_Tp &x) {
        while(!isdigit(ch = getchar_unlocked()));
        x = ch - '0';
        while(isdigit(ch = getchar_unlocked())) x = x * 10 + ch - '0';
        return *this;
    }
} cin;

struct ostream {
    char buf[60], top;
    inline ostream() : top(0) {}
    inline ostream &operator<<(char c) {
        putchar_unlocked(c);
        return *this;
    }
    inline ostream &operator<<(const string& s) {
        for(int i = 0; i < s.size(); i++) putchar_unlocked(s[i]);
        return *this;
    }
    inline ostream &operator<<(int x) {
        do buf[++top] = x % 10, x /= 10; while(x);
        while(top) putchar_unlocked(buf[top--] + '0');
        return *this;
    }
} cout;

int n, m, e, q;
int cnt[1 << N];
int to[2][1 << N];
bool ok[2][1 << N];
int sum[2][1 << N], f[3][1 << N];
int lg[1 << N];

void FWT(int a[]) {
    for(int k = 1; k < 1048576; k <<= 1) {
        int k2 = k << 1;
        for(int i = 0; i < 1048576; i += k2) {
            for(int j = 0; j < k; j++) {
                assert(i + j + k < 1048576);
                int x = a[i + j], y = a[i + j + k];
                a[i + j] = (x + y) % MOD;
                a[i + j + k] = ((ll)x - y + MOD) % MOD;
            }
        }
    }
}

void iFWT(int a[]) {
    for(int k = 1; k < 1048576; k <<= 1) {
        int k2 = k << 1;
        for(int i = 0; i < 1048576; i += k2) {
            for(int j = 0; j < k; j++) {
                assert(i + j + k < 1048576);
                int x = (ll)a[i + j] * 500000004 % MOD, y = (ll)a[i + j + k] * 500000004 % MOD;
                a[i + j] = (x + y) % MOD;
                a[i + j + k] = ((ll)x - y + MOD) % MOD;
            }
        }
    }
}

int a[N], b[N];

// #define FIO

int main() {

    #ifdef FIO
    freopen("bip.in", "r", stdin);
    freopen("bip.out", "w", stdout);
    #endif

    cin >> n >> n >> m >> e >> q;
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < m; i++) cin >> b[i];

    for(int i = 1; i <= e; i++) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        to[0][1 << u] |= (1 << v);
        to[1][1 << v] |= (1 << u);
    }

    for(int i = 1; i < (1 << max(n, m)); i++) cnt[i] = cnt[i ^ (i & -i)] + 1;
    for(int i = 2; i < (1 << max(n, m)); i++) lg[i] = lg[i >> 1] + 1;

    ok[0][0] = ok[1][0] = 1;
    for(int i = 1; i < (1 << n); i++) {
        if(i == (i & -i)) { ok[0][i] = cnt[to[0][i]] >= cnt[i]; continue; }
        int j = i & -i;
        to[0][i] = to[0][i ^ j] | to[0][j];
        ok[0][i] = cnt[to[0][i]] >= cnt[i];
    }
    for(int i = 1; i < (1 << m); i++) {
        if(i == (i & -i)) { ok[1][i] = cnt[to[1][i]] >= cnt[i]; continue; }
        int j = i & -i;
        to[1][i] = to[1][i ^ j] | to[1][j];
        ok[1][i] = cnt[to[1][i]] >= cnt[i];
    }

    for(int i = 1; i < (1 << n); i++) {
        for(int j = 0; j < n; j++) {
            if(~i & (1 << j)) continue;
            ok[0][i] = ok[0][i] && ok[0][i ^ (1 << j)];
        }
        if(ok[0][i]) sum[0][i] = sum[0][i ^ (i & -i)] ^ a[lg[i & -i]];
    }
    for(int i = 1; i < (1 << m); i++) {
        for(int j = 0; j < m; j++) {
            if(~i & (1 << j)) continue;
            ok[1][i] = ok[1][i] && ok[1][i ^ (1 << j)];
        }
        if(ok[1][i]) sum[1][i] = sum[1][i ^ (i & -i)] ^ b[lg[i & -i]];
    }

    for(int i = 0; i < (1 << n); i++) if(ok[0][i]) ++f[0][sum[0][i]];
    for(int i = 0; i < (1 << m); i++) if(ok[1][i]) ++f[1][sum[1][i]];

    FWT(f[0]);
    FWT(f[1]);
    for(int i = 0; i < (1 << 20); i++) f[2][i] = (ll)f[0][i] * f[1][i] % MOD;
    iFWT(f[2]);

    while(q--) {
        int x;
        cin >> x;
        cout << f[2][x] << '\n';
    }

    return 0;
}