题解：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}。因此答案为：

\begin{align}&\sum_{S_1}\sum_{S_1 \bigcap S_2=\varnothing}\binom{n_1+d-1}{m-b-1}\binom{n_2+d-1}{m-a-1}\\&=\sum_{S_1}\binom{n_2+d-1}{m-|S_1|-1}\sum_{S_1 \bigcap S_2=\varnothing}\binom{n_1+d-1}{m-|S_2|-1}\end{align}

其中 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 贡献再做一个高维前缀和即可。