容斥原理和概率与数学期望容斥原理和概率与数学期望

简介: 容斥原理和概率与数学期望

容斥原理

就是全集减去其他不满足的集合的并集,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);//算第一个集合的数个数
    int bs=b+(x==1)+(y==1);//算第二个集合的数个数
    int cs=c+(x==2)+(y==2);//算第三个集合的数个数
    int ds=d+(x==3)+(y==3);//算第四个集合的数个数
    if(as>=A&&bs>=B&&cs>=C&&ds>=D) return v=0;//假如找到了这个终点,返回0
    int sum=a+b+c+d+(x!=4)+(y!=4);
    sum=54-sum;//算剩下牌的个数
    if(sum<=0) return v=INF;//假如不够了,直接返回
    v=1;//初始化为1,因为是乘,所以初始化为1
    if(a<13) v+=(13.0-a)/sum*dp(a+1,b,c,d,x,y);//假如选A集合
    if(b<13) v+=(13.0-b)/sum*dp(a,b+1,c,d,x,y);//假如选B集合
    if(c<13) v+=(13.0-c)/sum*dp(a,b,c+1,d,x,y);//假如选C集合
    if(d<13) v+=(13.0-d)/sum*dp(a,b,c,d+1,x,y);//假如选D集合
    if(x==4)//假如小王能选
    {
        double t=INF;
        for(int i=0;i<4;i++) t=min(t,1.0/sum*dp(a,b,c,d,i,y));//枚举选哪个集合
        v+=t;
    }
    if(y==4)//假如大王能选
    {
        double t=INF;
        for(int i=0;i<4;i++) t=min(t,1.0/sum*dp(a,b,c,d,x,i));//枚举选哪个集合
        v+=t;
    }
    return v;
}
int main()
{
    cin>>A>>B>>C>>D;
    memset(f,-1,sizeof f);//初始化一个不存在的数
    double t=dp(0,0,0,0,4,4);//从初始状态开始跑
    if(t>INF/2) t=-1;
    printf("%.3lf\n",t);
    return 0;
}
相关文章
|
6月前
2572. 无平方子集计数(状态压缩dp)
2572. 无平方子集计数(状态压缩dp)
|
6月前
|
算法 测试技术 C#
【状态压缩 动态规划 数论】1799. N 次操作后的最大分数和
【状态压缩 动态规划 数论】1799. N 次操作后的最大分数和
|
6月前
考研高数之无穷级数题型一:判断收敛性、求收敛半径以及收敛域和收敛区间(题目讲解)
考研高数之无穷级数题型一:判断收敛性、求收敛半径以及收敛域和收敛区间(题目讲解)
325 0
|
算法
质数筛法:朴素素数筛,埃氏筛,欧式筛
质数筛法:朴素素数筛,埃氏筛,欧式筛
146 0
|
算法 C++
容斥原理算法的实现
容斥原理算法的实现
容斥原理算法的实现
|
算法
【贪心法】分数背包问题
【贪心法】分数背包问题
278 0
|
算法
绝对值不等式(贪心)
复习acwing算法基础课的内容,本篇为讲解基础算法:贪心——绝对值不等式,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上。
127 0
绝对值不等式(贪心)
|
人工智能 算法
排序不等式(贪心)
复习acwing算法基础课的内容,本篇为讲解基础算法:贪心——排序不等式,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上。
104 0
排序不等式(贪心)
|
机器学习/深度学习
【组合数学】递推方程 ( 常系数线性非齐次递推方程 的 非齐次部分是 多项式 与 指数 组合方式 | 通解的四种情况 )
【组合数学】递推方程 ( 常系数线性非齐次递推方程 的 非齐次部分是 多项式 与 指数 组合方式 | 通解的四种情况 )
210 0
|
机器学习/深度学习
【组合数学】递推方程 ( 非齐次部分是指数的情况 | 非齐次部分是指数的情况示例 )
【组合数学】递推方程 ( 非齐次部分是指数的情况 | 非齐次部分是指数的情况示例 )
141 0