【题解】AtCoder-ABC321-526互联

AtCoder-ABC321A 321-like Checker

依题意判断。

枚举 \(a_n\)，依题意模拟即可。

按长度搜。

将 \(b\) 排序，找到超过 \(p\) 的位置，前后分别算。

跳 \(x\) 的父亲，每次形如求 \(f(u,d)\) 表示 \(u\) 子树内距离 \(u\) 为 \(d\) 的节点个数，容易找到区间 \([L,R]\)，\(R\) 和 \(n\) 取 \(\min\) 即可，要特判 \(d\) 比较大的情况，细节偏多。

背包 DP 和物品顺序无关，所以删除可以看作最后一个加入 \(x\)，那么加入转移是 \(f_{i+x}\leftarrow f_{i+x}+f_i\)，删除就是 \(f_{i+x}\leftarrow f_{i+x}-f_i\)。

一个经典的连通容斥。

看到数据范围容易想到一个 \(O(3^n)\) 的枚举子集，问题现在变成求一个集合白点集合 \(S\) 连通的方案数，设为 \(h_S\)，首先 \(S\) 的红蓝点个数应当相等，记作 \(sum_S\)，容斥枚举 \(\mathrm{lowbit}(S)=x\) 所在集合 \(T\)，形如：

\[h_S=sum_S!-\sum_{T\subsetneq S,x\in T} h_T\times sum_{S\setminus T}! \]

之后就是把连通块拼起来，设 \(f_S\) 为连通块个数总和，\(g_S\) 为总方案数，这里防止算重也要加入 \(\mathrm{lowbit}(S)=x\) 所在集合 \(T\)，形如：

\[f_S\leftarrow f_{S\setminus T}\times h_T+g_{S\setminus T}\times h_T \]

\[g_S\leftarrow g_{S\setminus T}\times h_T \]

答案就是 \(\frac{1}{m!}f_S\)。