『容斥原理和广义容斥原理』

---

容斥原理

基础概念

我们假设有全集(S)，以及(n)个集合(A_1,A_2,...,A_n)，每个集合(A_i)中的元素具有性质(P_i)，现在我们要求不具有任何性质的集合大小，也就是元素个数，则具有如下的计算式：
[left |bigcap_{i=1}^noverline{A_i}right|=|S|+sum_{Tsubseteq{1,2,...,n},Tnot =emptyset}(-1)^{|T|}left | bigcap_{iin T}A_i right |]

当然，我们还具有另一种形式：

[left | bigcup_{i=1}^nA_i right |=sum_{Tsubseteq {1,2,...,n}}(-1)^{|T|-1}left | bigcap_{iin T} A_i right |]

这两种形式可以简单地互相转换得到，本质相同。

如何理解其组合意义，我们可以这样解释：

形式(1)：不具备任何性质的元素个数 (=) 就是元素总个数 (-) 至少具备一个性质的元素个数之和 (+) 至少具备两个性质的元素个数知和 (-) 至少具备三个性质的元素个数之和 (...)

形式(2)：所有集合的并集大小 (=) 所有集合的大小之和 (-) 每两个集合之间的交集大小 (+) 每三个集合之间的交集大小 (...)

毒瘤选举

Description

毒瘤选举大会开始了。选举大会的举办者Magolor不希望不毒瘤的人来当选，因为不毒瘤的人当选毒瘤领导人会让这次选举流芳百世、万人传颂，这是每个毒瘤都不想看到的。

因此，Magolor想要你(不管你是不是毒瘤)来帮他搞清楚有多大的概率这件事不会发生。毒瘤选举大会有(n)位选民和(k)位候选人。由于选民也是毒瘤，所以选民会随机投票(但幸好不会弃权或投多票)。一位候选人是毒瘤的当且仅当至少有一名选民给他投票。

现在，Magolor想知道在所有的投票方案中，有多少种方案满足: 所有候选人都是毒瘤的。因为方案数特别多，Magolor只需要你输出答案(bmod 998244363)的余数即可。

Input Format

第一行输入(T)表示有组(T)数据。

接下来行(T)每行两个整数: (n,k)。

Output Format

输出文件(T)行每行一个整数表示答案。

Sample Input

1
4 3

Sample Output

36

解析

我们可以把每一种投票方案看做一种元素，具备一个性质的元素就是有一个候选人没选的方案。那么我们就可以套用容斥原理的第一个模型：没有任何人落选的方案数就是全部方案数 (-) 至少有一个人落选的方案数之和 (+) 至少有两个人落选的方案数之和 (...)

那么我们的问题就是快速计算至少有(m)个人落选的方案数之和，显然，方案数即为：

[binom{k}{m}(k-m)^n]

那么根据容斥原理，答案即为：

[k^n+sum_{i=1}^m(-1)^ibinom{k}{i}(k-i)^n]

注意，模数是(998244363=3times 19times 97times 180547)，需要先根据每一个模数算一个答案，然后用中国剩余定理合并答案。组合数需要用(Lucas)定理计算，时间复杂度(O(ktimes(log_2 n+log_{mod}k)))。

从另一个角度考虑，(ans=k!times S(n,k))，所以对于(kgeq 180547)，答案为(0)，直接输出即可。

(Code:)

#include <bits/stdc++.h>
using namespace std;
const int N = 190000 , p[] = {0,3,19,97,180547};
int inv[5][N],fac[5][N],ans[5],n,m;
inline int add(int a,int b,int Mod) { return a + b >= Mod ? a + b - Mod : a + b; }
inline int mul(int a,int b,int Mod) { return 1LL * a * b % Mod; };
inline int sub(int a,int b,int Mod) { return a - b < 0 ? a - b + Mod : a - b; }
inline void Add(int &a,int b,int Mod) { a = add( a , b , Mod ); }
inline void Mul(int &a,int b,int Mod) { a = mul( a , b , Mod ); }
inline void Sub(int &a,int b,int Mod) { a = sub( a , b , Mod ); }
inline int quickpow(int a,int b,int Mod)
{
int res = 1;
for ( ; b ; Mul(a,a,Mod) , b>>=1 )
if ( 1 & b ) Mul(res,a,Mod);
return res;
}
inline void init(void)
{
for (int k=1;k<=4;k++)
{
fac[k][0] = inv[k][0] = 1;
for (int i=1;i<p[k];i++)
fac[k][i] = mul( fac[k][i-1] , i , p[k] );
inv[k][p[k]-1] = quickpow( fac[k][p[k]-1] , p[k]-2 , p[k] );
for (int i=p[k]-2;i>=1;i--)
inv[k][i] = mul( inv[k][i+1] , i+1 , p[k] );
}
}
inline int C(int n,int m,int k)
{
if ( n < m || n < 0 || m < 0 ) return 0;
int res = fac[k][n];
return mul( res , mul( inv[k][m] , inv[k][n-m] , p[k] ) , p[k] );
}
inline int Lucas(int n,int m,int k)
{
if ( m == 0 ) return 1;
int res = Lucas( n/p[k] , m/p[k] , k );
return mul( res , C( n%p[k] , m%p[k] , k ) , p[k] );
}
inline int Exeuclid(int a,int b,int &x,int &y)
{
if ( b == 0 ) return x = 1 , y = 0 , a;
int t = Exeuclid( b , a%b , x , y );
int _x = x , _y = y;
x = _y , y = _x - a / b * _y;
return t;
}
inline int ExCRT(void)
{
int M = p[1] , res = ans[1] % M , t , k , x , y;
for (int i=2;i<=4;i++)
{
k = ( (ans[i]-res) % p[i] + p[i] ) % p[i];
t = Exeuclid( M , p[i] , x , y );
x = x * (k/t) % (p[i]/t);
res = res + x * M;
M = M * p[i] / t;
res = ( res % M + M ) % M;
}
return res;
}
inline int solve(void)
{
for (int k=1;k<=4;k++)
{
ans[k] = quickpow( m , n , p[k] );
for (int i=1;i<=m;i++)
{
int val = mul( Lucas(m,i,k) , quickpow(m-i,n,p[k]) , p[k] );
if ( i & 1 ) Sub( ans[k] , val , p[k] );
else Add( ans[k] , val , p[k] );
}
}
}
int main(void)
{
init();
int T; long long N,M;
scanf("%d",&T);
while ( T --> 0 )
{
scanf("%lld%lld",&N,&M);
if ( M >= 180547 ) puts("0");
else n = N , m = M , solve(),
printf("%dn",ExCRT());
}
return 0;
}

小w的喜糖

Description

废话不多说，反正小w要发喜糖啦！！

小w一共买了n块喜糖，发给了n个人，每个喜糖有一个种类。这时，小w突发奇想，如果这n个人相互交换手中的糖，那会有多少种方案使得每个人手中的糖的种类都与原来不同。

两个方案不同当且仅当，存在一个人，他手中的糖的种类在两个方案中不一样。

Input Format

第一行，一个整数n

接下来n行，每行一个整数，第i个整数Ai表示开始时第i个人手中的糖的种类

对于所有数据，1≤Ai≤k,k<=N,N<=2000

Output Format

一行，一个整数Ans，表示方案数模1000000009

Sample Input

6
1
1
2
2
3
3

Sample Output

10

解析

首先我们认为同种糖的每一个也都是不同的，方便计数。

我们把一个方案看做一个元素，有一个人拿着原来和自己种类相同的糖看做满足一个性质，然后套用容斥原理(...)

那么我们就要计算所有人中至少有(i)个人拿着和自己同种糖的方案数，可以考虑(dp)计数。

设(f[i][j])代表前(i)种糖，有(j)个人拿着自己同种糖的方案数，可以直接转移：

[f[i][j]=sum_{k=0}^{min(j,cnt[i])}f[i-1][j-k]timesbinom{cnt[i]}{k}times cnt[i]^{underline{k}}]

组合意义：前(i-1)种糖中已经有(j-k)个人拿着自己同种的糖了，现在第(i)种糖这样的人要有(k)个，方案就是(cnt[i])个人中选(k)个人，第一个人有(cnt[i])种选择选到同种糖，第二个人有(cnt[i]-1)种可能选到同种糖(...)

设(m)为颜色总数，然后容斥：
[ans=sum_{i=0}^m(-1)^itimes f[m][i]times (n-i)!]

由于我们一开始把同种糖的每一个都看作本质不同的，所以最后要除掉每一种颜色出现次数的阶乘。

(Code:)

#include <bits/stdc++.h>
using namespace std;
const int N = 2020 , Mod = 1e9+9;
int n,m,a[N],cnt[N],f[N][N],fac[N],inv[N],ans;
inline int add(int a,int b) { return a + b >= Mod ? a + b - Mod : a + b; }
inline int mul(int a,int b) { return 1LL * a * b % Mod; };
inline int sub(int a,int b) { return a - b < 0 ? a - b + Mod : a - b; }
inline void Add(int &a,int b) { a = add( a , b ); }
inline void Mul(int &a,int b) { a = mul( a , b ); }
inline void Sub(int &a,int b) { a = sub( a , b ); }
inline int quickpow(int a,int b) { int res = 1; for (;b;Mul(a,a),b>>=1) if ( 1 & b ) Mul(res,a); return res; }
inline void input(void)
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
cnt[a[i]]++;
}
}
inline void init(void)
{
fac[0] = inv[0] = 1;
for (int i=1;i<=n;i++)
fac[i] = mul( fac[i-1] , i );
inv[n] = quickpow( fac[n] , Mod-2 );
for (int i=n-1;i>=1;i--)
inv[i] = mul( inv[i+1] , i+1 );
sort( cnt+1 , cnt+n+1 );
reverse( cnt+1 , cnt+n+1 );
for (int i=1;i<=n+1;i++)
if ( cnt[i] == 0 ) { m = i-1 ; break; }
}
inline int C(int n,int m) { return mul( fac[n] , mul( inv[m] , inv[n-m] ) ); }
inline int A(int n,int m) { return mul( fac[n] , inv[n-m] ); }
inline void DynamicProgram(void)
{
f[0][0] = 1;
for (int i=1,lim=cnt[1];i<=m;lim+=cnt[++i])
for (int j=0;j<=lim;j++)
for (int k=0;k<=min(cnt[i],j);k++)
Add( f[i][j] , mul( f[i-1][j-k] , mul( C(cnt[i],k) , A(cnt[i],k) ) ) );
}
inline void solve(void)
{
for (int i=0;i<=n;i++)
if ( i & 1 ) Sub( ans , mul( f[m][i] , fac[n-i] ) );
else Add( ans , mul( f[m][i] , fac[n-i] ) );
for (int i=1;i<=m;i++)
Mul( ans , inv[cnt[i]] );
}
int main(void)
{
input();
init();
DynamicProgram();
solve();
printf("%dn",ans);
return 0;
}

广义容斥原理

基础概念

用语言描述，容斥原理求的是不满足任何性质的方案数，我们通过计算所有至少满足(k)个性质的方案数之和来计算。

同样的，我们可以通过计算所有至少满足(k)个性质的方案数之和来计算恰好满足(k)个性质的方案数。这样的容斥方法我们称之为广义容斥原理。

容斥方法

首先，我们设(alpha(k))代表所有至少满足(k)的性质的方案数之和。

也就是说：

[alpha(0)=|S|\ \ alpha(1)=sum_{i}|A_i|\ \ alpha(2)=sum_{i,j}|A_icap A_j| \ ...\ \ alpha(k)=sum_{Tsubseteq{1,2,...,n},|T|=k}left | bigcap_{iin T}A_i right |]

我们发现(alpha(k))将具有(p(pgeq k))个性质的元素计算了(binom{k}{p})次。

假设(beta(k))代表恰好具有(k)个元素的方案数，则有递推公式如下：

[beta(k)=alpha(k)-sum_{i=k+1}^nbinom{i}{k}beta(i)]

组合意义就是我们把多算的那些方案数都减掉就可以了。

但是这样计算我们需要求出每一个(beta)的值，时间复杂度是(O(n^2))的。

我们有一个更好的计算式：

[beta(k)=sum_{i=k}^n(-1)^{i-k}binom{i}{k}alpha(i)]

这样就可以(O(n))计算单个(beta)的值了，我们现在来证明这个公式的正确性。

我们考虑具有(t)个的性质的元素被计算了几次：

(1.) 如果(t<k)，则该元素一次都没有被计算过。

(2.) 如果(t=k)，则该元素恰好被计算了一次。

(3.) 如果(t>k)，(......)真复杂

那么现在我们要证明，当(t>k)时，具有(t)个性质的元素没有被计算过。

根据上面提到的(alpha)中多算的次数，我们容易得知具有(t)个性质的元素被计算了这么多次：

[sum_{i=k}^t(-1)^{i-k}binom{i}{k}binom{t}{i}]

利用三项式系数恒等式，我们对此进行化简：

[sum_{i=k}^t(-1)^{i-k}binom{i}{k}binom{t}{i}\ \ =sum_{i=k}^t(-1)^{i-k}binom{t}{k}binom{t-k}{i-k}\ \ = binom{t}{k}sum_{i=k}^t(-1)^{i-k}binom{t-k}{i-k}\ \ = binom{t}{k}sum_{i=0}^{t-k}(-1)^{i}binom{t-k}{i}]

根据二项式定理，我们构造：
[(1-x)^{t-k}=sum_{i=0}^{t-k}(-x)^ibinom{t-k}{i}]

令(x=1)，我们得知：

[sum_{i=0}^{t-k}(-1)^{i}binom{t-k}{i}=0]

所以，当(t>k)时，具有(t)个性质的元素没有被计算过。那么我们就可以愉快地容斥了。

集合计数

Description

一个有N个元素的集合有2 ^ N个不同子集（包含空集），现在要在这2^N个集合中取出若干集合（至少一个），使得它们的交集的元素个数为K，求取法的方案数，答案模1000000007。（是质数喔~）

Input Format

一行两个整数N，K。

Output Format

一行为答案。

Sample Input

3 2

Sample Output

6

解析

当这些集合具有一个元素的交集的时候，我们就认为这种方案具有一个性质，那么我们要求的就是具有(k)个性质的元素个数，是广义容斥原理计算的对象。

那么我们现在只需考虑如何计算至少具有(k)个性质的元素个数即可。

首先，我们只要强制选(k)个元素，使他们成为交集的一部分，然后剩下的随便选，这样的方案就一定具有(k)个元素以上的交集。

那么就可以这样计算了：

[alpha(k)=binom{n}{k}2^{2^{n-k}}]

组合意义：首先我们选(k)个元素有(binom{n}{k})种方案，剩下的元素可选可不选，可以组成(2^{n-k})个子集，每个子集可选可不选，就有(2^{2^{n-k}})种方案了。

直接使用公式计算(beta(k))的值即可。

(Code:)

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+20 , Mod = 1e9+7;
int n,k,alpha[N],fac[N],inv[N],Pow[N],ans;
inline int add(int a,int b) { return a + b >= Mod ? a + b - Mod : a + b; }
inline int mul(int a,int b) { return 1LL * a * b % Mod; };
inline int sub(int a,int b) { return a - b < 0 ? a - b + Mod : a - b; }
inline void Add(int &a,int b) { a = add( a , b ); }
inline void Mul(int &a,int b) { a = mul( a , b ); }
inline void Sub(int &a,int b) { a = sub( a , b ); }
inline int quickpow(int a,int b) { int res = 1; for (;b;Mul(a,a),b>>=1) if ( 1 & b ) Mul(res,a); return res; }
inline void init(void)
{
fac[0] = inv[0] = Pow[0] = 1;
for (int i=1;i<=n;i++)
fac[i] = mul( fac[i-1] , i ) , Pow[i] = Pow[i-1] * 2LL % (Mod-1);
inv[n] = quickpow( fac[n] , Mod-2 );
for (int i=n-1;i>=1;i--)
inv[i] = mul( inv[i+1] , i+1 );
}
inline int C(int n,int m) { return mul( fac[n] , mul( inv[m] , inv[n-m] ) ); }
inline void solve(void)
{
for (int i=0;i<=n;i++)
alpha[i] = mul( C(n,i) , quickpow( 2 , Pow[n-i] ) );
for (int i=k;i<=n;i++)
if ( ( i - k ) & 1 ) Sub( ans , mul( C(i,k) , alpha[i] ) );
else Add( ans , mul( C(i,k) , alpha[i] ) );
}
int main(void)
{
scanf("%d%d",&n,&k);
init();
solve();
printf("%dn",ans);
return 0;
}

已经没有什么好害怕的了

Description

有糖果和药片各(n)个。糖果(i)有能量(a_i)，药片(i)有能量(b_i)。

你需要将药片和糖果两两配对，求有多少种方案满足糖果比药片能量大的组数减去药片比糖果能量大的组数恰好为(k)。

保证所有的能量两两不同，答案对(10^9+9)取模。

Input Format

第一行两个整数(n,k)。

第二行(n)个整数，表示糖果的能量。

第三行(n)个整数，表示药片的能量。

Output Format

输出一行一个整数，表示方案数。

Sample Input

4 2
5 35 15 45
40 20 10 30

Sample Output

4

解析

首先，我们设糖果能量大于药片能量有(x)组，药片能量大于糖果能量有(y)组，那么符合题意的方案应该满足：
[begin{cases}x+y=n\ x-y=kend{cases}]

很容易得知，(n+k)为奇数的时候无解，反之(x=frac{n+k}{2})。

那么我们假设存在一组糖果能量大于药片能量就具有一个性质，原问题就是要求具有(frac{n+k}{2})个性质的方案数。

套用广义容斥原理的方法，我们需要计算具有至少(k)个性质的方案数。

我们需要把糖果盒药片先排一下序，然后考虑(dp)计算方案。设(f[i][j])代表前(i)个糖果，有(j)个糖果的能量大于药片的方案数，容易写出状态转移方程：
[f[i][j]=f[i-1][j]+f[i-1][j-1]times (cnt[i]-(j-1))]

其中(cnt[i])代表比第(i)个糖果能量小的药片的数量。

容易得知：(alpha(k)=f[n][k]times(n-k)!)，套用广义容斥原理计算(beta)即可。

(Code:)

#include <bits/stdc++.h>
using namespace std;
const int N = 2020 , Mod = 1e9+9;
int n,k,a[N],b[N],C[N][N],fac[N];
int alpha[N],f[N][N],cnt[N],ans;
inline int add(int a,int b) { return a + b >= Mod ? a + b - Mod : a + b; }
inline int mul(int a,int b) { return 1LL * a * b % Mod; };
inline int sub(int a,int b) { return a - b < 0 ? a - b + Mod : a - b; }
inline void Add(int &a,int b) { a = add( a , b ); }
inline void Mul(int &a,int b) { a = mul( a , b ); }
inline void Sub(int &a,int b) { a = sub( a , b ); }
inline int quickpow(int a,int b) { int res = 1; for (;b;Mul(a,a),b>>=1) if ( 1 & b ) Mul(res,a); return res; }
inline void input(void)
{
scanf("%d%d",&n,&k);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
for (int i=1;i<=n;i++) scanf("%d",&b[i]);
}
inline void init(void)
{
int p = 0; fac[0] = 1;
for (int i=1;i<=n;i++)
{
fac[i] = mul( fac[i-1] , i );
while ( p < n && b[p+1] < a[i] ) p++;
cnt[i] = p;
}
C[0][0] = C[1][0] = C[1][1] = 1;
for (int i=2;i<=n;i++)
{
C[i][0] = C[i][i] = 1;
for (int j=1;j<i;j++)
C[i][j] = add( C[i-1][j-1] , C[i-1][j] );
}
}
inline void DynamicProgram(void)
{
for (int i=0;i<=n;i++) f[i][0] = 1;
for (int i=1;i<=n;i++)
for (int j=1;j<=i;j++)
f[i][j] = add( f[i-1][j] , mul( f[i-1][j-1] , max( cnt[i]-j+1 , 0 ) ) );
}
inline void solve(void)
{
k = ( n + k ) / 2;
for (int i=1;i<=n;i++)
alpha[i] = mul( f[n][i] , fac[n-i] );
for (int i=k;i<=n;i++)
if ( ( i - k ) & 1 ) Sub( ans , mul( C[i][k] , alpha[i] ) );
else Add( ans , mul( C[i][k] , alpha[i] ) );
}
int main(void)
{
input();
if ( ( n + k ) & 1 )
return puts("0") , 0;
sort( a+1 , a+n+1 );
sort( b+1 , b+n+1 );
init();
DynamicProgram();
solve();
printf("%dn",ans);
return 0;
}

---