0918
<=1>=8的情况。
<=1X>=8Y组排列。那么通过容斥原理来解决就可以写成：
即：
二.
n0121次，这样的序列有多少种？
同样的，我们转向它的逆问题。也就是不出现这些数字的序列不出现其中某些数字的序列。
Ai(i=0…2)i的序列数，那么由容斥原理，我们得到该逆问题的结果为：
可以发现每个Ai的值都为2^n(因为这些序列中只能包含两种数字)。而所有的两两组合
都110。(因为它不包含数字，所以不存在)
要记得我们解决的是它的逆问题，所以要用总数减掉，得到最终结果：
三.
方程整数解问题
给出一个方程：
其中
。
求这个方程的整数解有多少组。
我们先不去理会xi<=8的条件，来考虑所有正整数解的情况。这个很容易用组合数来求解，我们要把20个元素分成6组，也就是添加5块“夹板”，然后在25个位置中找5块“夹板”的位置。
然后通过容斥原理来讨论它的逆问题，也就是x>=9时的解。
我们定义Ak为xk>=9并且其他xi>=0时的集合，同样我们用上面的添加“夹板”法来计算Ak的大小，因为有9个位置已经被xk所利用了，所以：
然后计算两个这样的集合Ak、Ap的交集：
因为所有x的和不能超过20，所以三个或三个以上这样的集合时是不能同时出现的，它们的交集都为0。最后我们用总数剪掉用容斥原理所求逆问题的答案，就得到了最终结果：
四.
求指定区间内与n互素的数的个数：
nr[1;r]n互素的数的个数。
n互素的数的个数。
npi(i=1…k)
[1;r]pi整除呢？它就是：
然而，如果我们单纯将所有结果相加，会得到错误答案。有些数可能被统计多次(被好几个素因子整除)。所以，我们要运用容斥原理来解决。
我们可以用2^k的算法求出所有的pi组合，然后计算每种组合的pi乘积，通过容斥原理来对结果进行加减处理。
关于此问题的最终实现：
int solve (int n, int r)
{
vector p;
for (int i=2; i*i<=n; ++i)
if (n % i == 0)
{
p.push_back (i);
while (n % i == 0)
n /= i;
}
if (n > 1)
p.push_back (n);
int sum = 0;
for (int msk=1; msk
{
int mult = 1,
bits = 0;
for (int i=0; i
if (msk & (1<
{
++bits;
mult *= p[i];
}
int cur = r / mult;
if (bits % 2 == 1)
sum += cur;
else
sum -= cur;
}
return r - sum;
}
五.
素数四元组的个数问题
个数
，从其中选出4个数，使它们的最大公约数为1，问总共有多少中取法。
我们解决它的逆问题：求最大公约数d>1的四元组的个数。
运用容斥原理，将求得的对于每个d的四元组个数的结果进行加减。
其中deg(d)代表d的质因子个数，f(d)代表四个数都能被d整除的四元组的个数。
求解f(d)时，只需要利用组合方法，求从所有满足被d整除的ai中选4个的方法数。
然后利用容斥原理，统计出所有能被一个素数整除的四元组个数，然后减掉所有能被两个素数整除的四元组个数，再加上被三个素数整除的四元组个数…
六.
和睦数三元组的个数问题
。选出a,
b, c (其中2<=a
· 或者满足，
，
·或者满足
首先，我们考虑它的逆问题：也就是不和睦三元组的个数。
然后，我们可以发现，在每个不和睦三元组的三个元素中，我们都能找到正好两个元素满足：它与一个元素互素，并且与另一个元素不互素。
所以，我们只需枚举2到n的所有数，将每个数的与其互素的数的个数和与其不互素的数的个数相乘，最后求和并除以2，就是要求的逆问题的答案。
2n2n所有数的结果，分别求解显然效率太低。
2n所有数的结果。
在这里，我们可以使用改进的埃拉托色尼筛法。
·首先，对于2到n的所有数，我们要知道构成它的素数中是否有次数大于1的，为了应用容斥原理，我们还有知道它们由多少种不同的素数构成。
deg[i]igood[i]truefalsei1是否成立。
i2ndeg[]igood[]false。
·然后，利用容斥原理，求出2到n每个数的cnt[i]：在2到n中不与i互素的数的个数。
回想容斥原理的公式，它所求的集合是不会包含重复元素的。也就是如果这个集合包含的某个素数多于一次，它们不应再被考虑。
igood[i]=trueii*ji*jN/ii*jideg[i]deg[i]为奇数，那么我们要用加号，否则用减号。
程序实现：
int n;
bool good[MAXN];
int deg[MAXN], cnt[MAXN];
long long solve()
{
memset (good, 1, sizeof good);
memset (deg, 0, sizeof deg);
memset (cnt, 0, sizeof cnt);
long long ans_bad = 0;
for (int i=2; i<=n; ++i)
{
if (good[i])
{
if (deg[i] == 0) deg[i] = 1;
for (int j=1; i*j<=n; ++j)
{
if (j > 1 && deg[i] == 1)
if (j % i == 0)
good[i*j] = false;
else
++deg[i*j];
cnt[i*j] += (n / i) * (deg[i]%2==1 ? +1 : -1);
}
}
ans_bad += (cnt[i] - 1) * 1ll * (n - cnt[i] - 1);
}
return (n-1) * 1ll * (n-2) * (n-3) / 6 - ans_bad / 2;
}未完待续……
