Hello, Codeforces! The reason why I am writing this blog is that my ACM/ICPC teammate calabash_boy is learning this technique recently(he is a master in string algorithms,btw), and he wanted me to provide some useful resources on this topic. I found that although many claim that they do know this topic well, problems concerning inclusion-exclusion principle are sometimes quite tricky and not that easy to deal with. Also, after some few investigations, the so-called "Inclusion-Exclusion principle" some people claim that they know wasn't the generalized one, and has little use when solving problems. So, what I am going to pose here, is somewhat the "Generalized Inclusion-Exclusion Principle".
Consider a finite set X and three subsets A, B, C, To obtain 
, we take the sum 
+ 
+ 
. Unless A, B, C are pairwise distinct, we have an overcount, since the elements of 
has been counted twice. So we subtract 
. Now the count is correct except for the elements in 
which have been added three times, but also subtracted three times. The answer is therefore
, or equivalently,
The following formula addresses the case applied to more sets.
Let A1, A2, ..., An be subsets of X. Then
This is a formula which looks familiar to many people, I'll call it The Restricted Inclusion-Exclusion Princinple, it can convert the problem of calculating the size of the union of some sets into calculating the size of the intersection of some sets.
