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;
}
|