题目链接
题目解法
感觉不难啊，怎么想到网络流和 \(hall\) 定理后面就屁都没想到呢
首先一眼网络流
先二分答案
考虑一个朴素的建图方法是：把每个人拆成 \(k\) 个点，然后往在的天连边，跑最大流，满流即合法
可以发现，跑网络流对这道题还说没有必要，因为只要判是否有完美匹配
不难想到 \(hall\) 定理，定理具体自己查
观察到 \(n\le 18\)，所以考虑状压状物
考虑每个点拆分成的 \(k\) 个点连出去的边都相同，所以如果只包含了 \(i\) 拆分出去的一个点，一定不够极限，所以需要枚举的点集要么不包含 \(i\) 拆分的点，要么包含所有的 \(k\) 个点
当前天是邻边当且仅当它包含的人的集合与枚举的人的集合有交集
可以想到在补集上做文章，即补集与枚举的人的集合不交，不难发现可以高位前缀和优化
时间复杂度 \(O(n2^n\log nk)\)
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
int FF=0,RR=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
return FF*RR;
}
const int N=18;
int n,k,a[N],f[1<<N];
int main(){
n=read(),k=read();
F(i,0,n-1) a[i]=read();
int l=0,r=4000000;
while(l<r-1){
int mid=(l+r)>>1;
F(S,0,(1<<n)-1) f[S]=0;
F(i,1,mid){
int st=0;
F(j,0,n-1) if(~((i-1)/a[j])&1) st|=1<<j;
f[st]++;
}
F(i,0,n-1) F(S,0,(1<<n)-1) if(!(S>>i&1)) f[S^1<<i]+=f[S];
bool flg=1;
F(i,0,(1<<n)-1) if(__builtin_popcount(i)*k>mid-f[(1<<n)-1-i]){ flg=0;break;}
if(!flg) l=mid;
else r=mid;
}
printf("%d\n",r);
fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
return 0;
}