The 2024 ICPC Asia East Continent Online Contest (II) K. Match（图计数dp 二分图匹配方案）

题目

长为n(n<=200)的数组a和b，给定一个k(k<2^60)，

只要ai异或bj>=k，i和j就连一条边，

对于任意x∈[1,n]，求二分图匹配数恰为x的方案数，答案对998244353取模

思路来源

https://qoj.ac/submission/585586

题解

维护一个多项式，表示二分图匹配数恰为0,1,...,x的方案数

考虑每一位，递归下去，然后自底往上合并，

合并的时候要乘以组合数，

先选择左边z个点是哪些点，右边z个点是哪些点，然后乘上二者匹配的顺序z的阶乘

考虑左边的点和右边的点是在二进制第几位的时候连的边，

连边的时候需要显式地比k大

如果当前这位k是1的话，ai异或bj不能是0，所以只能递归下去匹配

k是0的话都有可能，要么递归下去被匹配，

要么没匹配，回溯上来用没匹配的在这一位变成1匹配

复杂度O(n^4)，但常数比较小

代码

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=1e3+5,mod=998244353;
int n,fac[N],C[N][N];
ll k;
void add(int &x,int y){x=(x+y)%mod;
}
vector<int> work(int t, vector<ll> f, vector<ll> g) {vector<int> ans(f.size() + g.size() + 1, 0LL);if (t == - 1 || f.empty() || g.empty()) {for (int i = 0; i <= f.size(); i += 1) {ans[i] = 1ll * C[f.size()][i] * C[g.size()][i] % mod * fac[i] % mod;}return ans;}vector<ll> a, b, c, d;for (auto it : f){if (it >> t & 1) a.push_back(it); else b.push_back(it);}for (auto it : g){if (it >> t & 1) c.push_back(it);else d.push_back(it);}if (k >> t & 1) { //ai^bj>=k ai^bj这一位只能为1vector<int> ans1 = work(t - 1, a, d);vector<int> ans2 = work(t - 1, b, c);for (int i = 0; i < ans1.size(); i += 1) {for (int j = 0; j < ans2.size(); j += 1) {add(ans[i + j], 1ll * ans1[i] * ans2[j] % mod);}}} else { // ai^bj>=k ai^bj=0或1 先递归0的情况 然后考虑合并1的情况vector<int> ans1 = work(t - 1, a, c); // ivector<int> ans2 = work(t - 1, b, d); // jfor (int i = 0; i < ans1.size(); i += 1) {for (int j = 0; j < ans2.size(); j += 1) {for (int x = 0; x + i <= a.size() && x + j <= d.size(); x += 1) {for (int y = 0; y + i <= c.size() && y + j <= b.size(); y += 1) {add(ans[i + j + x + y] , 1ll * ans1[i] * ans2[j] % mod* C[a.size() - i][x] % mod * C[d.size() - j][x] % mod * C[c.size() - i][y] % mod * C[b.size() - j][y] % mod * fac[x] % mod * fac[y] % mod);}}}}}return ans;
}int main() {fac[0] = C[0][0] = 1;for (int i = 1; i < N; i++) {fac[i] = 1ll * fac[i - 1] * i % mod;C[i][0] = C[i][i] = 1;for (int j = 1; j < i; j++) {C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;}}cin >> n >> k;vector<ll> a(n, 0);auto b = a;for (auto &it : a) cin >> it;for (auto &it : b) cin >> it;vector<int> ans = work(60, a, b);for (int i = 1; i <= n; i ++) {cout << ans[i] << '\n';}
}