Inclusion–exclusion principle

Wiki:Inclusion–exclusion principle

Statement:

Example:

一个正整数序列a[1],a[2],a[3]...,a[n]，一定存在一个x,y使得a[x]+a[x+1]+..+a[y]是n的倍数。

proof:构造前n'项和S[n'],则出现两种情况：1)S[k']是n的倍数 2)S[k']对n的余数必然属于{1,2,..n-1}

则至少会出现两个余数相同的值，那么这两个前缀和的差即为若干项之和且能整除n，得证

例: poj3370.cpp 

Exercise:

1.poj3695

题意：求若干个矩形(<=20)的面积并，10w次查询

思路：容斥原理，查询次数比状态总数少，dfs+剪枝即可，状态枚举会超时

Code: poj3370.cpp

2.[Scoi2010day1]幸运数字

题意：求10^10内某个区间内，是由6,8,66,68,86,88等数字倍数组成数的个数

思路：先枚举出这些由6,8组成的数字，跟筛法一样去掉不必要的数字，然后根据容斥原理dfs

Code: [Scoi2010day1]幸运数字.cpp 

还有几个组合数学的题，虽跟容斥原理没关系，就当练练手吧：

poj1019.cpp lower_bound + math

poj1496.cpp Combinactorics

poj1833.cpp next_permulation()

poj1850.cpp dp or Combinactorics

poj1942.cpp water

poj2084.java BigInteger+Combinactorics

poj3252.cpp dp or Combinactorics