题解：P14196 [ICPC 2024 Hangzhou R] Japanese Bands

神秘题。设 $S$ 是所有有相关限制的数的集合。

设 $S_1$ 是只在左边出现的数的集合，$S_2$ 是只在右边出现的数的集合，那么有 $S\setminus S1 \setminus S2$ 是同时出现在两边的数的集合（显然应该有 $S_1 \bigcap S_2=\varnothing$）。设 $a=|S_1|,b=|S_2|,c=|S\setminus S1 \setminus S2|,d=m-a-b-c$。$d$ 代表了没有施加限制的数的个数，这些数可以任意选择。

考虑此时的方案数，左边的选择是把 $n_1$ 切成 $a+c$ 个不可空和 $d$ 个可空集，预先给这 $d$ 个集合加上 1 后插板可得 $\binom{n_1+d-1}{a+c+d-1}=\binom{n_1+d-1}{m-b-1}$。同理右边是 $\binom{n_2+d-1}{b+c+d-1}=\binom{n_2+d-1}{m-a-1}$。因此答案为：

其中 $S_1,S_2$ 其实不是随便取的。容易发现在左边和右边一一连边的情况下，没连到的边其实是 $S_1$ 内部的边和 $S_2$ 内部的边。因此如果把 $k$ 条限制建图，我们不能要求有一条边的两个端点同时出现在同一边。换言之，$S_1$ 和 $S_2$ 都是独立集。

求出独立集集合是简单的，记一个数组 $f$，对于每条边 $(u,v)$，将 $f_{2^{u-1} \operatorname{or}2^{v-1}}$ 加 1，然后做高维前缀和，最终 $f=0$ 的那些状态就是独立集。这是好理解的，因为这相当所有 $(2^{u-1} \operatorname{or}2^{v-1})$ 的超集（同时出现 $u$ 和 $v$ 的点集）都不合法。

额外的，那些没有施加限制的点也不能进入 $S_1,S_2$，因此还要对每个没有施加限制的点 $x$，对 $2^{x-1}$ 的超集加 1。

现在求出了 $S_1,S_2$ 的取值范围，我们先预处理对于每个 $S_2$ 的贡献 $\binom{n_1+d-1}{m-|S_2|-1}$，然后枚举 $S_1$，发现后面那个 $\sum$ 就是 $S_1$ 的补集子集和。对 $S_2$ 贡献再做一个高维前缀和即可。