这种神仙东西菜鸡果然学不来
1.[BZOJ2440] 完全平方数
题意: 询问第 k 个无平方因子数
二分一个数 $x$, 那么他在他在整个序列中的位置就是 $x$- 含一个质因数的平方的因子的数 + 含两个质因数的平方的因子的数 $\cdots$
可以发现容斥系数正是 $\mu$ 函数, 所以就变成了 $\sum_{i=1}^{\lfloor\sqrt{x}\rfloor}\mu(i)\frac{x}{i*i}$
2.[BZOJ2863] 愤怒的元首
题意: 询问 $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$
3.[BZOJ2839] 集合计数
题意: 一个有 $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)$
4.[BZOJ3622] 已经没有什么好害怕的了
题意: 给出两数列 $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$
来源: http://www.bubuko.com/infodetail-2898848.html