年 更 大 作
FJOI2017 矩阵填数
\(\max =v\) 拆成 \(\le v\) 和存在一个 \(=v\)，对第二个条件容斥发现变成 \(<v\)，离散化后对每个点求出上界直接算。复杂度 \(O(n^32^n)\)。
CF449D
相当于每一位上至少有一个 \(0\)。钦定某些位上全是 \(1\)，发现只需要做高维后缀和。
FMT 即可。复杂度 \(O(a_i\log a_i)\)。当然也有手拆 FMT 摁做的方法。
ZJOI2016 小星星
\(f(u,j,S)\) 表示 \(u\) 为根的子树，恰好用 \(S\) 以内的这些数，\(p_u=j\) 的方案数。
你可以直接在转移的时候做集合不交并卷积，但是我们可以容斥：排列看作所有数至少出现一次，钦定某些元素不能出现，然后对每个集合 \(S\) 做一遍 \(O(n^3)\) 树形 DP（即 \(f(u,j)\) 表示 \(u\) 子树内，且 \(p_u=j\) 的方案数，但这里要求 \(j\not\in S\)），设得到的值是 \(g(S)\)，则答案为 \(\sum(-1)^{|S|}g(S)\)。
时间复杂度 \(O(n^32^n)\)，空间复杂度 \(O(n^2)\)。
集合不相等容斥
计数符合以下条件的 \(a\) 的数量：
- \(\forall i,a_i\in S_i\)。
- \(\forall i\neq j,a_i\neq a_j\)。
考虑建出 \(n\) 点的图，若 \(a_i=a_j\) 则连无向边 \((i,j)\)。那么互不相同相当于图中一条边都不能连。
设 \(C(E)\subseteq 2^V\) 为连上边集 \(E\) 后的连通块集合，\(F(P)\) 表示连通块形态为 \(P\) 时的答案（\(P\subseteq 2^V\)），则答案为
\[\sum_{E}(-1)^{|E|}F(C(E))=\sum_{P}F(P)\sum_{C(E)=P}(-1)^{|E|} \]不难发现重点在计算后面那一项。显然各个连通块独立，只需要对每个连通块 \(S\in P\)，求出所有使 \(S\) 以内点集联通的边集 \(E\) 的 \((-1)^{|E|}\) 之和。设 \(f_k\) 表示 \(k\) 个点的方案数，发现没有联通限制的时候答案是 \([k=1]\)，即 \((\exp f)_k=[k=1]\)，取 \(\ln\) 得到 \(f_k=(-1)^{k-1}(k-1)!\)，因此
\[ANS=\sum_{P}F(P)\prod_{S\in P}(-1)^{|S|-1}(|S|-1)! \]具体来说，考虑怎么算 \(f\)：较好理解的方式是采用容斥，用随意连的贡献和减去不连通的贡献和。由于随意连的时候贡献和为 \([k=1]\)，不连通时考虑 \(1\) 所在连通块，有
\[f_i=[i=1]-\sum_{j=1}^{i-1}\binom{i-1}{j-1}f_j[i-j=1]=-(i-1)f_{i-1} \]再结合 \(f_1=1\)，自然有 \(f_k=(k-1)!(-1)^{k-1}\)。当然，你可以发现上述过程就是做了一次 \(\ln\)。
集合幂级数优化 exp 即可做到 \(O(n^22^n)\)。
ABC236Ex
\(F(P)=\prod_{S\in P}\lfloor\frac{M}{\text{lcm}(S)}\rfloor\) 容易计算。
本题中 \(F(P)\) 对各个连通块独立，某些题目中则不满足这个性质。
集训队互测 2012 calc
把元素划分为相等集合之后，有 \(F(P)=\prod_{S\in P}\sum_{i=1}^ki^{|S|}\)。
接下来我们简记为 \(F_x=(-1)^{x-1}(x-1)!\sum_{i=1}^ki^x\)。考虑 \(F\) 的 EGF，只需要求 \([x^n]\text{exp }F\)。
由于 \(n\) 比较小，暴力算 \(\text{exp}\) 就是 \(O(n^2)\)。
算自然数幂可以预处理第二类斯特林数后 \(O(n^2)\) 计算，总的复杂度为 \(O(n^2)\)。
ABC288Ex
如果没有不降的限制，可以数位 DP 在 \(O(N^3\log M)\) 的时间内求出 \(1,2,\cdots,N\) 个数时的答案。
现在考虑怎么处理不降。考虑钦定某些位置是 \(=\)，某些位置是 \(<\)。
发现相当于对这 \(N\) 个数进行划分，划分出的集合内部两两相同，不同集合中的数两两不同。
从每个奇数大小的集合中选一个代表元，考虑怎么算 \(g(i)\) 表示 \(i\) 个数两两不同的方案数。
使用集合不相等容斥；发现这个异或和的限制没办法把连通块拆开，但是偶数大小的连通块方案数直接就是 \(M+1\)，奇数大小的连通块若有 \(x\) 个，方案数是 \(F(x)\)，其中 \(F(x)\) 表示 \(x\) 个 \(\le M\) 的数 \(\text{xor sum}=X\) 的方案数。重新设 \(h(x,y)\) 表示 \(x\) 个数划分成若干连通块，其中 \(y\) 个大小为奇数的容斥系数和；转移类似于求个 exp，枚举 \(1\) 所在连通块大小，有
\[h(x,y)=\sum_{i=1}^xh(x-i,y-(i\bmod 2))\times(-1)^{i-1}(i-1)!\times\binom{x-1}{i-1} \]可以做到 \(O(N^3)\)。那么 \(g(i)=\sum h(i,y)F(y)\)。最终相当于要在 \(g\) 的基础上，从 \([0,M]\) 中选出 \(2i\) 个数，且每个数的出现次数均为偶数。插板可得方案数 \(\binom{M+i}{i}\)。于是答案即
\[\sum_{i=0}^{\lfloor N/2\rfloor}\frac{g(N-2i)}{(N-2i)!}\binom{M+i}{i} \]总的复杂度是 \(O(N^3\log M)\)。好像有 \(O(N\log M)\) 做法但是我不会/hsh
标签：连通,技巧,sum,容斥,反演,exp,集合,复杂度 From： https://www.cnblogs.com/YunQianQwQ/p/17261419.html