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". Most of the describing text are from the graduate text book Graduate Text in Mathematics 238, A Course in Enumeration, and the problems are those that I encountered in real problem set, so if possible, I'll add a link to the real problem so that you can solve it by yourself. I'll start with the basic formula, one can choose to skip some of the text depending on your grasp with the topic.
Consider a finite set 
and three subsets 
, To obtain 
, we take the sum 
+ 
+ 
. Unless 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.
The Restricted Inclusion-Exclusion Principle. Let 
be subsets of . Then
This is a formula which looks familiar to many people, I'll call it The Restricted Inclusion-Exclusion Principle, 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. It's not hard to prove the correctness of this formula, we can just check how often an element 
is counted in both sides. If 
, then it's counted once on either side. Suppose 
, and more precisely, that 
is in exactly 
of the sets 
. The count on the left-hand side is 
, and on the right hand side, we have
for 
, thus the equality holds.
Example 1. Let's see an example problem Co-prime where this principle could be applied: Given 
, you need to compute the number of integers in the interval 
such that is coprime with 
, that is, 
. There are 
testcases. Constraints: 
, 
.
such that 
, then the answer is 
. How we're gonna compute 
and then find all prime factors 
of 
be the set of numbers that are divisible by 
, then the answer is the 
, which may be hard to compute directly. However, using the restricted inclusion-exclusion principle, we can convert the problem into computing the size of the intersection of sets, which is trivial. Time complexity is 
, with 
equals to the number of distinct prime factors of The standard interpretation leads to the principle of inclusion-exclusion. Suppose we are given a set , called the universe, and a set 
of properties that the elements of may or may not process. Here we can define the properties as we like, such as 
, 
, or even 
. Let Ai be the subset of elements that enjoy property 
(and possibly others). Then 
is the number of elements that process none of the properties. Clearly, 
is the set of elements that possess the properties 
(and maybe others). Using the notation
we arrive at the inclusion-exclusion principle.
Inclusion-Exclusion Principle. Let be a set, and a set of properties. Then
The formula becomes even simpler when 
depends only on the size 
. We can then write 
for 
, and call 
a homogeneous set of properties, and in this case 
also depends only on the cardinality of 
. Hence for homogeneous properties, we have
This is the very essence of Inclusion-Exclusion Principle . Please make sure you understand every notation before you proceed. One can figure out, by letting 
, we arrive at the restricted inclusion-exclusion principle.
Example 2. This problem Character Encoding requires you to compute the number of solutions to the equation 
, satisfying that 
, modulo 
. Constraints: 
. Hint: the number of non-negative integer solutions of 
is given by 
.
. To do that, we apply the inclusion-exclusion principle. Let 
, then 
is our desired answer. Clearly, this set of properties is homogeneous. Take 
, then 
is the number of solutions with 
. Setting 
, and it's the same as the number of solutions of the system 
, due to precomputing factorials and the modular inverses of factorials.Example 3. Well, this one is a well-known problem. K-Inversion Permutations. The statement is neat and simple. Given N, K, you need to output the number of permutations of length N with K inversions, taken modulo 
. Constraint: 
.
as the number of permutations of length 
with 
inversions. The recurrence is also trivial: 
. This is 
, then 
, then the number of solutions to the equation is 
. Therefore, we can group those sets together. By inclusion-exclusion principle, $N_{=\varnothing}=\sum\limits_{k=0}^{n}(-1)^{k}\binom{n}{k} N_{\geq k}=\sum\limits_{
