容斥原理
容斥原理:其实就是不断的加减来得到最终结果的过程。
容斥原理例题1:Devu和鲜花
题意:有n(n<=20)个花瓶,每个花瓶里有Ai枝花,现要取M枝花组成一束,有多少种方案。
分析:这是容斥原理的经典例题。
假设我们在第i个花瓶里取
a
i
a_{i}
ai枝花,我们可以得到式子:
x
1
+
x
2
+
…
+
x
n
=
M
x_{1}+x_{2}+…+x_{n}=M
x1+x2+…+xn=M
我们这里用一个技巧,假设
y
i
y_{i}
yi=
x
i
+
1
x_{i} +1
xi+1
y
1
+
y
2
+
…
+
y
n
=
M
+
N
y_{1}+y_{2}+…+y_{n}=M+N
y1+y2+…+yn=M+N
这时,我们原来的问题就变成了这个题的解的个数。
而且,此时
y
i
>
=
1
y_{i}>=1
yi>=1,然后我们就可以用隔板法。
(注:这里隔板隔得是每个块的数量,因为每次隔板不能从最两端放(操作起来比较方便),所以我们必须将这个数换成>=1的才行)
此时,我们接着分析:
现在我们假设每个瓶里面的花都是:
∞
\infty
∞
这时我们发现种类数是:
C
M
+
N
−
1
N
−
1
C_{M+N-1}^{N-1}
CM+N−1N−1
然后我们去思考如何除去不符合题意的部分:
这里就是用到了我们的容斥了,首先确定一下当前的答案: C M + N − 1 N − 1 C_{M+N-1}^{N-1} CM+N−1N−1-( S 1 S_{1} S1 ∪ \cup ∪ S 2 S_{2} S2 ∪ \cup ∪ … … … ∪ \cup ∪ S n S_{n} Sn)
这里的 S i S_{i} Si表示的是第i个花瓶取>=Ai+1的情况。
这里的容斥就体现的很明显了:我们先算有1个不符合情况的,然后再算两个,这样的话就是加上奇数的,减去偶数的,就可以得到答案。
具体的计算和算整体的类似,我们以1个不满足的时候为例:
Σ i = 1 i = n \Sigma_{i=1}^{i=n} Σi=1i=n C N + M − 1 − ( A i + 1 ) N − 1 C_{N+M-1-(Ai+1)}^ {N-1} CN+M−1−(Ai+1)N−1,这里可能会有疑问为什么这里是Ai+1而不是Ai+2,我们不是将xi转化为yi了?就是因为这个是隔板法,每次取的是>=1我们每次都放N-1个板,这样就能保证每次都从每个花瓶里取1个。一定保证之前取完的是不合法的。
下面是AC代码:
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 20, mod = 1e9 + 7;
LL A[N];
int down = 1;
//快速幂求逆元
int qmi(int a, int k, int p)
{
int res = 1;
while (k)
{
if (k & 1) res = (LL)res * a % p;
a = (LL)a * a % p;
k >>= 1;
}
return res;
}
//求组合数
int C(LL a, LL b)
{
if (a < b) return 0;
int up = 1;
for (LL i = a; i > a - b; i -- ) up = i % mod * up % mod;
return (LL)up * down % mod;//除以某个数等于乘以他的逆元
}
int main()
{
LL n, m;
cin >> n >> m;
for (int i = 0; i < n; i ++ ) cin >> A[i];
for (int j = 1; j <= n - 1; j ++ ) down = (LL)j * down % mod;//求down
down = qmi(down, mod - 2, mod);//求down的逆元
int res = 0;
for (int i = 0; i < 1 << n; i ++ )
{
LL a = m + n - 1, b = n - 1;
int sign = 1;
for (int j = 0; j < n; j ++ )
if (i >> j & 1)
{
sign *= -1;//每次转换加减,偶数个就加上,因为这里是从0开始,所以我们不用对res赋初值,整体就是偶数加上,奇数减去(分析我们推导出的式子)。
a -= A[j] + 1;
}
res = (res + C(a, b) * sign) % mod;
}
cout << (res + mod) % mod << endl;
return 0;
}
例题2:Character Encoding
题意:有m个格子,要求填数,每个数的范围是[0,n-1],要求最终的数是k。
分析:这是容斥原理的经典例题。不过这个题的话和上面的题还是有所不同的,我们对比发现这个数据量是很大的不可能用上面那个枚举的方法,但是这个题的优秀之处在于他的每个空格的能放的最大数是相同的,我们直接用 C m i C_{m}^{i} Cmi来表示我们选几个合格即可,整体思路和上面的相同,这里不再赘述,下面是AC代码:
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
#define int long long
const int mod=998244353;
const int N=1e6+10;
int n,m,k;
int qpow(int a,int b)
{
int t=1;
while(b)
{
if(b&1) t=t*a%mod;
a=a*a%mod;
b>>=1;
}
return t;
}
int fc[N],gc[N];
int mul(int a,int b)
{
return a*b%mod;
}
inline void init(){
fc[0]=1;
for(int i=1;i<=500001;i++) fc[i]=mul(fc[i-1],i);
gc[500001]=qpow(fc[500001],mod-2);
for(int i=500001;i>=1;i--) gc[i-1]=mul(gc[i],i);
}
inline int C(int i,int j){
if(j>i)return 0;
return mul(mul(fc[i],gc[j]),gc[i-j]);
}
int cal()
{
int ans=0;
for(int i=1;i*n<=k;i++)
{
if(i&1) ans=(ans+C(m,i)*C(k+m-1-i*n,m-1))%mod;
else ans=(ans-C(m,i)*C(k+m-1-i*n,m-1))%mod;
}
return (C(k+m-1,m-1)-ans+mod)%mod;
}
signed main()
{
init();
int t;
cin>>t;
while(t--)
{
cin>>n>>m>>k;
cout<<cal()<<endl;
}
return 0;
}
例题3:810975
题意:一共n场比赛,赢了m场,连续赢得场数为k,问有多少中可能。
题解:可以转化为和第2道题一样的思路。
但是我们先朴素的分析一下题目,一共n场比赛赢了m场,连续赢得场数为k,如果直接处理的话(可以自己想一想)这个连续的k场真的很难处理,所以这个对于1很难处理我们就去处理0。发现这里有n-m个0,这时我们就在这n-m个0中插入1,由与0的两边可以插,所以一共相当于有n-m+1个空档。
所以问题就转化成了n-m+1个格字,填数,每个格子填的最大的数是k,之和是m。问有几种方案,这时这个题目就和上面是一样的了。
当然,想到这里之后还是不够的,这样算了之后是最大时<=k的时候,而不是恰好等于k的时候,而且k是必须含有的。
这里我们用cal(k)-cal(k-1)即可。
简单证明一下:cal(k-1)是每个都<=k-1的情况,cal(k)是每个都<=k-1的时候。这样的话,其实每个都<=k-1的时候cal(k-1)是全部都包含的。只有==k时候是不包含的,所以这里可以表示。
下面是AC代码:
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
#define int long long
const int mod=998244353;
const int N=1e6+10;
int n,m,k;
int qpow(int a,int b)
{
int t=1;
while(b)
{
if(b&1) t=t*a%mod;
a=a*a%mod;
b>>=1;
}
return t;
}
int fc[N],gc[N];
int mul(int a,int b)
{
return a*b%mod;
}
inline void init(){
fc[0]=1;
for(int i=1;i<=500001;i++) fc[i]=mul(fc[i-1],i);
gc[500001]=qpow(fc[500001],mod-2);
for(int i=500001;i>=1;i--) gc[i-1]=mul(gc[i],i);
}
inline int C(int i,int j){
if(j>i)return 0;
return mul(mul(fc[i],gc[j]),gc[i-j]);
}
int cal(int k)
{
int ans=0;
for(int i=1;i*(k+1)<=m;i++)
{
if
上一篇:
[离散数学] 容差原理
下一篇:
第 36 章 数论--公差原理
推荐阅读
-
线性可微支持向量机的原理推导 最大化几何区间 d 公式分析
-
SpringCloud--持久层框架MyBatis Plus的使用方法和原理详解--V.MyBatis Plus 使用总结
-
Java HashMap 的数据结构和基本原理及其在 Jdk8、Jdk11 和 Jdk17 中的一些变化,以及一些常见问题。
-
微控制器原理与应用
-
Redis 完全指南:命令与原理 - 4. 基本命令
-
深入了解 Java 中的 ThreadLocal 机制,了解其工作原理、优缺点分析、数据库连接管理的应用、使用注意事项
-
Spring Boot 异步任务、任务调度和异步请求线程池的用法和原理
-
数据结构顺序表:从原理到 C 语言实现
-
电力电子技术 03 交直流整流器 (2) - 单相半波整流二极管不受控整流 - II.用于电阻电感负载的半波整流器的工作原理
-
51 微控制器智能社区安防系统 [proteus 仿真 + 程序 + 报告 + 原理图 + 演示视频]。