容斥原理表示形式(Representation of inclusion exclusion principle)

容斥原理对于大多数人来说是一个原理,因为这个事实太显然了,你想想,满足某一个条件的元素个数-满足某二个条件的元素个数+满足某三个条件的元素个数显然是对的。于是大多数人就这么去把它当做一个原理去套了,然后被毒瘤出题人折磨致死。

所以这个东西是需要证明的。其实容斥原理就是一种反演。因为你是用至少满足某几个条件的方案数来推出刚好满足某几个条件的方案数。令f(sta) = 至少满足sta条件的方案数 令g(sta) = 刚好满足sta条件的方案数)如果是至少,那么f(sta) = sigma g(ista) (ista & sta = sta)则 g(空) = f(空) – f(1) – f(2) – f(3) … + f(1,2) + f(2,3)…这个就显然多了对吧。。。。。。相应的g(sta) = sigma( (-1)|tmp| * f(sta | tmp) , tmp & sta = 0)

这就是容斥原理的基本形式。————————————————版权声明:本文为CSDN博主「69160394」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。原文链接:https://blog.csdn.net/qq_69160394/article/details/124723453

————————

The inclusion exclusion principle is a principle for most people, because this fact is too obvious. When you think about it, the number of elements satisfying a certain condition – the number of elements satisfying a certain two conditions + the number of elements satisfying a certain three conditions is obviously right. So most people take it as a principle, and then they are tortured to death by the person who made the question of cancer.

So this thing needs to be proved. In fact, the inclusion exclusion principle is a kind of inversion. Because you use the number of schemes that meet at least some conditions to deduce the number of schemes that just meet some conditions. Let f (STA) = the number of schemes that at least satisfy the sta condition let g (STA) = the number of schemes that just satisfy the sta condition) if it is at least, then f (STA) = sigma g (ISTA) (ISTA & sta = STA) then G (empty) = f (empty) – f (1) – f (2) – f (3)… + F (1,2) + F (2,3)… This is obviously more, right…… Corresponding g (STA) = sigma ((-1) |tmp| * f (STA | TMP), TMP & sta = 0)

This is the basic form of the inclusion exclusion principle———————————————— Copyright notice: This article is the original article of CSDN blogger “69160394”, which complies with the CC 4.0 by-sa copyright agreement. Please attach the original source link and this notice for reprint. Original link: https://blog.csdn.net/qq_69160394/article/details/124723453