zcmimi's blog

arrow_back容斥共16篇文章

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

先考虑每种硬币可以用无数次

f_i表示金额为i有多少种方案

f_i = \sum_{j=1}^4 f_{i-c[j](i \ge c_j)}

我们再来考虑硬币使用次数有限制怎么办

不合法的情况有:

1超额

1,2超额

1,3超额

1,4超额

1,2,3超额

1,2,4超额

1,3,4超额

1,2,3,4超额

...

要注意的是在多种硬币限制的情况下可能会减去多次,或加上多次

比如1超额,2超额,(1,2同时超额被减去两次,这是就要加回来

(1,2,3)(1,2,4)又是多算的...

是不是更直观的了解了容斥?

为了方便,我们可以枚举二进制下状态来更加优美实现。

(当有奇数种不合法的时候减去,偶数种不合法时加上)

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

这个显然是错排问题

A_ii在位置i上的所有排列

ans=|\overline A_1\bigcap \overline A_2 \bigcap ...\bigcap \overline A_n|

=|N|

-(|A_1|+|A_2|+...+|A_n|)

+(|A_1\bigcap A_2|+...+|A_{n-1}\bigcap A_n|)

-\ ...

+ (-1)^n |A_1\bigcap A_2\bigcap ... \bigcap A_n

=n!- {n\choose 1}\cdot (n-1)! + {n\choose 2}\cdot (n-2)! - ...\ + (-1)^n {n\choose n}

=n!(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+...+(-1)^n\frac{1}{n!}) = D_n

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

第二类斯特林数

n个不同的球放进m个相同的盒子,保证盒子非空,求方案数。

容斥法:

S(n,m)=\frac 1{m!}\sum_{i=0}^m {m\choose i}(m-i)^n(-1)^i

枚举空盒个数,剩下随便放,到这里开始也有了二项式反演的形式

由于盒子相同,所以除以m!

递推法:

S(n,m)=S(n-1,m-1)+mS(n-1,m)

相当于考虑现在要放的求是否单独在一个盒子里:

  1. 不占一盒:

    其余n-1个球放到m-1个盒子里

  2. 放到某个有球的盒子里:

    m个盒子可放(m种可能),其余n-1个球放到m个盒子里

此题要求的是S(n,m) \mod 2

m为偶数,S(n,m) \equiv S(n-1,m-1)

m为奇数,S(n,m) \equiv S(n-1,m-1)+s(n-1,m)

这样的话,相当于:

(x,y)y为奇数时,可以走到(x+1,y+1)(a变换

否则可以走到(x+1,y+1)(a变换,或(x+1,y)(b变换

求从(0,0)走到(n,m)的方案数\mod 2

这个过程必然走了ma变换,走了n-mb变换

b变换只能在偶数位置出现,那么变换的序列必然是如下形式:

a,b\times ?,a,a,b\times ?,a,a,...,a

也就是在\frac {m+1}2个间隔中插入n-mb,即隔板法

方案数:C(n-m+\frac{m+1}2-1,\frac{m+1}2 -1) \mod 2

还有一个结论:仅当n\&m==m时,C(n,m) \equiv 1 \bmod 2

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

g_i表示交集个数至少为i的方案数

那么g_i = {n\choose i}(2^{2^{n-i}}-1)

先从n中选i个,然后其他可以随便取

那就是有2^{n-i}个集合可以取

然后又可以取至少1个集合

那么答案就是{n\choose i}(2^{2^{n-i}}-1)

f_i表示恰好为i

那么g_k=\sum_{i=k}^n f_i\cdot {i\choose k}

反演f_k=\sum_{i=k}^n g_i\cdot{i\choose k} (-1)^{i-k}

不能直接快速幂,因为指数不能\mod p,要用2^{2^i}=(2^{2^{i-1}})^2倒着枚举算

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

题意:

给出一个矩阵,要求每行只能选一个节点,每列选的节点不能超过所有选的节点的一半,不能不选, 给出每个节点的选择方案数,求总方案数

解法

考虑到限制是每列选择的不能超过一半,我们可以想到不合法的最多只有一列

我们可以用总方案数减去不符合的

s_i=\sum_{j=1}^m a_{ij}

总方案数:\prod_{i=1}^n (s_i+1) - 1

\because k=\frac {tot}2

所以我们有一个很妙的方法:

设选中目标行之外的权值+1,不选+0,选中目标行权值位+2

最后只要权值> n,那么目标行一定被选了超过\frac n2

f(i,k)表示总共选了i次(也就是选到第i行)权值为k的方案数

f(i,k) += f(i-1,k)*(s_i-a_{ij})(当前行不选目标列

f(i,k+1) += f(i-1,k)(当前行完全不选

f(i,k+2) += f(i-1,k)\times a_{ij}(当前行选中目标列

ans = \prod_{i=1}^n (s_i+1) - 1 - \sum_{i=n+1}^{2n} f(n,i)

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

先将b数组从小到大排序

设选中了xa > b,由总对数为n,由x-(n-x)=k,可以知道x=\frac{n+k}2

我们设f(i,j)为前ia中选中了ja > b的方案数

那么f(i,j)=f(i-1,j)+f(i-1,j-1)\times(l_i-j+1)

(l_i表示b中小于a_i的最后一个位置)

但是还有剩下的n-x

我们可以设g_i表示a>b对数\ge i的方案数

那么g_i = f(n,i) \times (n-i)!(相当于剩下的随便排列组合)

我们设f_i表示a>b对数恰好为i对的方案数

那么g_k = \sum_{i=k}^n f_i \times {i\choose k} (相当于从恰好i个方案中选k对出来)

经过二项式反演可以知道:

f(k)=\sum_{i=k}^n(-1)^{i-k}{i\choose k}g(i)

2/2
Search
search