这种神仙东西菜鸡果然学不来
题意：询问第k个无平方因子数
二分一个数$x$，那么他在他在整个序列中的位置就是$x$-含一个质因数的平方的因子的数+含两个质因数的平方的因子的数$\cdots$
可以发现容斥系数正是$\mu$函数，所以就变成了$\sum_{i=1}^{\lfloor\sqrt{x}\rfloor}\mu(i)\frac{x}{i*i}$
题意：询问$n$个点的图中$Dag$的个数
设$f_i$表示$i$个点的组成$Dag$的个数，$g_i$表示至少$i$个点入度为0的个数
因为$Dag$去掉若干个出度为$0$的点仍为$Dag$，所以可求得：
$g_i=f_{n-i}\binom{n}{i}2^{i(n-i)}$
怎么求出来的？可以这让考虑，我们首先选出来$i$个点，强制它们的出度为$0$，因为剩下的$n-i$点向它们连边后仍为$Dag$，所以枚举这$i(n-i)$条边连不连
求出来$g_i$之后，根据容斥的套路求$f_i$：
$f_i=\sum_{j=1}^i(-1)^{j-1}g_j$
题意：一个有$n$个元素的集合有$2^n$个不同子集（包含空集），现在要在这$2^n$个集合中取出若干集合（至少一个），使得它们的交集的元素个数为$k$，求取法的方案数
我们枚举它的交集$k$，一共有$\binom{n}{k}$种方案，然后剩下的无论怎么取交集一定为空
交集空集=总数-至少一个交集+至少两个交集-$\cdots$
则答案可表示为$ans=\binom{n}{k}\sum_{i=0}^{n-k}(-1)^i\binom{n}{i}(2^{2^{n-i}}-1)$
题意：给出两数列$A$,$B$都有$n$个元素, 元素两两互不相同, 问有多少种方案使得恰好($a[i]>b[j]$的数目)$-$($a[i]<b[j]$的数目)$= k$?
转化一下问题，设有$x$对$a_i>b_j$，那么$x-(n-x)=k$，解得：$x=\frac{n+k}{2}$，所以我们应该求出恰好$x$对$a_>b_j$的个数
一眼是容斥，不过并不影响我不会做。首先根据套路，我们显然是要求出至少有$i$对$a_i>b_j$
一般来说，容斥题目中所谓至少就是先固定住$i$个而让剩下的随便选，所以我们设$dp_{ij}表示选了$i$对至少有$j$对$a>b$的方案数
如果做过一个叫$RabbitNumering$的题就知道这个$dp$应该在排好序后做，我们设$s_i$表示比$a_i$小的$b$的数目
然后转移方程即为$dp_{ij}=dp_{i-1j}+dp_{i-1j-1}*(s_i-j+1)$
设$f_i$表示恰好有$i$对$a>b$的方案数，$g_i$表示至少有$i$对$a>b$的方案数
因为我们是固定$i$对$a>b$，剩下的随意匹配，所以有：$g_i=dp_{ni}*(n-i)!$
考虑$f_i$在$g_j$（$i>=j$）中出现了$\binom{i}{j}$次，就有$g_i=\sum_{j=i}^{n}\binom{j}{i}f(j)$
根据二项式反演得：$f_i=\sum_{j=i}^n(-1)^{(j-i)}\binom{j}{i}g_j$
原文：https://www.cnblogs.com/Slrslr/p/10182929.html