容差原理与概率和数学期望 容差原理与概率和数学期望 容差原理与概率和数学期望 容差原理与概率和数学期望
容斥原理
就是全集减去其他不满足的集合的并集，E-(E1∪E2∪E3∪.....∪Ek)=E-E1-E2-E3-...+E1∩E2+E2∩E3..意思是奇数个的符号就是-，偶数个就是+，一般用二进制枚举来求所有的其他∩，一个数中二进制的1的个数就是元素∩的个数，然后看个数在判断符号即可
1.Devu和鲜花
214. Devu和鲜花 - AcWing题库
1.假设全集
不满足的情况：
S1相当于先给A1集合选A1+1支花，然后其余的限制跟全集一样做就行就是C(M+N-1-(Ai+1))(N-1)
S1∩S2就是先在A1集合选A1+1，A2集合选A2+1花，然后其余的限制跟全集一样做就行了就是C(M+N-1-(A1+1)-(A2+1))(N-1)
然后用二进制枚举集合就行了，1代表有这个集合，假如1的个数是奇数就-，偶数就+
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=25,mod=1e9+7; ll n,m; 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%mod; a=(ll)a*a%mod; k>>=1; } return res; } int C(ll a,ll b)//求C(a,b) { if(a<b) return 0; ll up=1; for(ll i=a;i>a-b;i--) up=(ll)i%mod*up%mod;//分子的数 return (ll)up*down%mod;//分子除分母，相当于乘逆元 } int main() { scanf("%lld%lld",&n,&m); for(int i=0;i<n;i++) scanf("%lld",&A[i]); for(int i=1;i<=n-1;i++) down=(ll)i*down%mod;//先预处理出来n-1的阶层 down=qmi(down,mod-2,mod);//求逆元 int res=0; for(int i=0;i<(1<<n);i++)//二进制枚举 { ll a=n+m-1,b=n-1;//获取整个的大小 int sign=1;//符号，假如及数个就-，偶数就+ for(int j=0;j<n;j++)//枚举那个集合被选了 if((i>>j)&1)//假如这位是1 { a-=A[j]+1;//先给这个集合分配a[j]+1个 sign*=-1;//符号变一下 } res=(res+sign*C(a,b))%mod; } cout<<(res+mod)%mod<<endl; return 0; }
2.破译密码
215. 破译密码 - AcWing题库
莫比乌斯函数，用来解决容斥原理的符号问题
在筛质数的时候求出来
相当于问（x’，y'）=1，也即互质的数的个数，可以用欧拉函数求出来，这里用容斥原理来求
用总的个数-有一个公因子的个数+有两个公因子的个数-...+...
最多分成2根号a段数，每一段的数都是相等的
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=50010; int primes[N],cnt; bool st[N]; int mobius[N],sum[N];//mobius函数跟他的前缀和 void init(int n)//筛质数 { mobius[1]=1; for(int i=2;i<=n;i++) { if(!st[i]) { primes[cnt++]=i; mobius[i]=-1;//只有一个质因子 } for(int j=0;primes[j]*i<=n;j++) { int t=primes[j]*i; st[t]=true; if(i%primes[j]==0) { mobius[t]=0; break; } mobius[t]=mobius[i]*-1; } } for(int i=1;i<=n;i++) sum[i]=sum[i-1]+mobius[i];//求前缀和 } int main() { init(N-1); int T; scanf("%d",&T); while(T--) { int a,b,d; scanf("%d%d%d",&a,&b,&d); a/=d,b/=d;//先映射到a',b' int n=min(a,b); ll res=0; for(int l=1,r;l<=n;l=r+1)//枚举l,r { r=min(n,min(a/(a/l),b/(b/l)));//（a/l）,(b/l)就是g(x) res+=(sum[r]-sum[l-1])*(ll)(a/l)*(b/l); } printf("%lld\n",res); } return 0; }
概率与数学期望
就是弄出递推公式，然后用记忆化搜索来做，递推公式就是期望公式
1.绿豆蛙的归宿
217. 绿豆蛙的归宿 - AcWing题库
#include<bits/stdc++.h> using namespace std; const int N=100010,M=200010; int n,m; int h[N],e[M],ne[M],w[M],idx; int dout[N];//记录出度，也即连到他的边有多少 double f[N]; void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } double dp(int u) { if(f[u]>=0) return f[u];//假如算过了，直接返回 f[u]=0; for(int i=h[u];~i;i=ne[i]) { int j=e[i]; f[u]+=(w[i]+dp(j))/dout[u];//递推公式 } return f[u]; } int main() { scanf("%d%d",&n,&m); memset(h,-1,sizeof h); for(int i=0;i<m;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c); dout[a]++; } memset(f,-1,sizeof f);//double让他为-1，也即全部都是false，也即没数的意思 printf("%.2lf\n",dp(1)); return 0; }
2.扑克牌
218. 扑克牌 - AcWing题库
#include<bits/stdc++.h> using namespace std; const int N=14; const double INF=1e20; int A,B,C,D; double f[N][N][N][N][5][5]; double dp(int a,int b,int c,int d,int x,int y) { if(a>13||b>13||c>13||d>13) return INF;//假如越界 double &v=f[a][b][c][d][x][y]; if(v>=0) return v;//假如算过了 int as=a+(x==0)+(y==0);//算第一个集合的数个数上一篇： linux 为指定挂载点分配未分配空间