题解

前置知识：Hall定理，高维前缀和

首先很容易可以建一个二分图，左边$n \le 20$个点是每种人，右边$m$个点表示座位。原点到左边的点的权值$=$有多少人，如果左边某种人可以坐那个作为就连接一个权值为1的边。现在就是问这个二分图匹配能不能把左边流量流满。

考虑Hall定理，枚举一个左边的集合$S$，设$f(S)=\sum_{i\in S} a_i$，那么我们就需要查询$[1,m]$中有多少整数至少可以被$S$中的一个整除，设为$g(S)$。根据Hall定理，如果$\forall S\subseteq [n],f(S)\ge g(S)$，就说明可以匹配，输出Yes

现在的问题是计算$g$根据容斥原理，$g(S)=\sum_{T\subseteq S} (-1)^{|T|+1} h(T)$其中$h(T)$表示$[1,m]$中是$T$所有元素的倍数的数的个数。$h(T)=\lfloor {m\over \prod_{k\in T} b_k}\rfloor$。$g$是$(-1)^{|T|+1}h(T)$的高维前缀和，使用FWT优化即可。

总复杂度$O(n2^n)$不使用FWT是$O(n2^n+3^n)$