标签：组合 min text sum max Leftrightarrow binom
- 二项式反演
\[f(n) = \sum_{i=0}^n\binom{n}{i}g(i) \Leftrightarrow g(n) = \sum_{i=0}^n(-1)^{n-i}\binom{n}{i}f(i)
\]
其中 \(f\) 为恰好，\(g\)为至多。（可以用于随便选）
\[f(n) = \sum_{i=n}^m\binom{i}{n}g(i) \Leftrightarrow g(n) = \sum_{i=n}^m(-1)^{i-n}\binom{i}{n}f(i)
\]
其中 \(f\) 为恰好，\(g\)为至少。（固定 \(x\) 个，剩余任选）
- 莫比乌斯反演
\[f(n) = \sum_{d|n}g(d) \Leftrightarrow g(n) = \sum_{d|n}\mu(\frac{n}{d})g(d)
\]
\[I(d) = 1, \varepsilon(d) = [d=0], id(d) = d
\]
\[\mu * I = \varepsilon
\]
\[\phi * I = id
\]
- 斯特林反演
\[S_1(n,m) = S_1(n-1,m-1)+S_1(n-1,m)*(n-1)
\]
\[S_2(n,m) = S_2(n-1,m-1)+S_2(n-1,m)*m
\]
\[x^{\overline n}=\sum_{i=0}^n S_1(n,i)x^i
\]
\[x^{n}=\sum_{i=0}^n S_2(n,i)x^{\underline i}
\]
\[x^{n}=\sum_{i=0}^n (-1)^{n-i} S_2(n,i)x^{\overline i}
\]
\[x^{\underline n}=\sum_{i=0}^n (-1)^{n-i} S_1(n,i)x^{i}
\]
\[F(n) = \sum_i S_2(n,i) G(i) \Leftrightarrow G(n) = \sum_i (-1)^{n-i} S_1(n,i) F(i)
\]
\[F(n) = \sum_i S_1(n,i) G(i) \Leftrightarrow G(n) = \sum_i (-1)^{n-i} S_2(n,i) F(i)
\]
- \(\text{Min}-\text{Max}\) 容斥
\[\max(S) = \sum_{T \in S}(-1)^{|T|+1}\min(T)
\]
\[\min(S) = \sum_{T \in S}(-1)^{|T|+1}\max(T)
\]
\[E(\max(S)) = \sum_{T \in S}(-1)^{|T|+1}E(\min(T))
\]
\[E(\min(S)) = \sum_{T \in S}(-1)^{|T|+1}E(\max(T))
\]
\[\text{kth}-\max(S)=\sum_{T \in S} (-1)^{|T|-k}\binom{|T|-1}{k-1}\min(T)
\]
\[E(\text{kth}-\max(S))=\sum_{T \in S} (-1)^{|T|-k}\binom{|T|-1}{k-1}E(\min(T))
\]
\[\text{kth}-\min(S)=\sum_{T \in S} (-1)^{|T|-k}\binom{|T|-1}{k-1}\max(T)
\]
\[E(\text{kth}-\min(S))=\sum_{T \in S} (-1)^{|T|-k}\binom{|T|-1}{k-1}E(\max(T))
\]
- 杜教筛
\[(f*g) = h \to f(n) = \sum_{i=0}^n h(i) - \sum_{i=2}^n g(i)f(\left\lfloor\frac{n}{i}\right\rfloor)
\]
- 类欧
\[f(a,b,c,n) \gets f(c,c-b-1,a,\left\lfloor\frac{a*n+b}{c}\right\rfloor-1)
\]
- 二次剩余
\[x^2 = n \pmod p
\]
\[\text{find} \; a^2 - n \; [(a^2-n)^{\frac{p-1}{2}}=-1]
\]
\[i^2 = a^2 - n
\]
\[(a+i)^{p+1} = n \pmod p
\]
- 互不相等容斥：将相等元素连边，每个连通块分开计算，记 \(f(P)\) 表示连通块形态为 \(P\) 的答案，\(g(S)\) 表示一个连通块 \(S\) 的容斥系数，则 $ans = \sum_T f(T) \prod_{S \in T} g(S) $。
考虑 \(g\) 的计算方法，其组合意义表示：\(\sum_E (-1)^|E|\)，其中 \(E\) 是使得 \(S\) 内联通的全局边集。容斥掉联通的限制，发现不联通只有在一个点的时候答案为 \(1\) 否则为 \(0\)，再考虑 \(\text{不连通} = \exp \text{联通}\)，故得到 \(g(S) = (-1)^{|S|-1}(|S|-1)!\)
\(f\) 根据题目具体而定，一般分为连通块是否互相影响考虑。
子集枚举为 \(3^n\)，可以集合幂级数优化到 \(2^n n^2\)。
标签：组合,
min,
text,
sum,
max,
Leftrightarrow,
binom
From： https://www.cnblogs.com/Anonymely/p/18541561