容斥原理 训练笔记

容斥原理

设S是一个有限集,A_1,A_2…A_n是S的n个子集,则

∣ S − ⋃ i = 1 n A i ∣ = ∑ i = 0 n ( − 1 ) i ∑ 1 ≤ j 1 < j 2 . . . < j i ≤ n ∣ ⋂ k = 1 i A j k ∣ |S-\bigcup_{i=1}^{n}A_i|=\sum_{i=0}^{n}(-1)^i\sum_{1\leq j_1< j_2...<j_i \leq n}|\bigcap_{k=1}^{i}A_{j_k}| Si=1nAi=i=0n(1)i1j1<j2...<jink=1iAjk

基本应用:

m件不同的物品,分给n个人,要求每一个人至少分得一件物品,求不同的分配方案数

A i A_i Ai表示第i个人没有物品, S S S表示 m m m个物品分给 n n n个人的总方案数

∣ S − ⋃ i = 1 n A i ∣ = ∑ i = 0 n ( − 1 ) i ∑ 1 ≤ j 1 < j 2 . . . < j i ≤ n ∣ ⋂ k = 1 i A j k ∣ |S-\bigcup_{i=1}^{n}A_i|=\sum_{i=0}^{n}(-1)^i\sum_{1\leq j_1< j_2...<j_i\leq n}|\bigcap_{k=1}^{i}A_{j_k}| Si=1nAi=i=0n(1)i1j1<j2...<jink=1iAjk

= ∑ i = 0 n ( − 1 ) i ( n i ) ( n − i ) m =\sum_{i=0}^{n}(-1)^i\binom{n}{i}(n-i)^m =i=0n(1)i(in)(ni)m

2 n 2n 2n个元素 a 1 , a 2 , . . . , a n a_1,a_2, ...,a_n a1,a2,...,an b 1 , b 2 , . . . , b n b_1,b_2, ...,b_n b1,b2,...,bn,求有多少个它们的全排列,满足任意的

1 ≤ i ≤ n 1 \leq i \leq n 1in, a i a_i ai b i b_i bi 都不相邻。

同样的,令 A i A_i Ai表示 a i a_i ai b i b_i bi相邻,

∣ S − ⋃ i = 1 n A i ∣ = ∑ i = 0 n ( − 1 ) i ∑ 1 ≤ j 1 < j 2 . . . j i ≤ n ∣ ⋂ k = 1 i A j k ∣ |S-\bigcup_{i=1}^{n}A_i|=\sum_{i=0}^{n}(-1)^i\sum_{1\leq j_1< j_2...j_i \leq n}|\bigcap_{k=1}^{i}A_{j_k}| Si=1nAi=i=0n(1)i1j1<j2...jink=1iAjk
= ∑ i = 0 n ( − 1 ) i ( n i ) ∣ 有 i 对相邻的方案数 ∣ =\sum_{i=0}^{n}(-1)^i\binom{n}{i}|有i对相邻的方案数| =i=0n(1)i(in)i对相邻的方案数
= ∑ i = 0 n ( − 1 ) i ( n i ) 2 i ∗ ( 2 n − i ) ! =\sum_{i=0}^{n}(-1)^i\binom{n}{i}2^i*(2n-i)! =i=0n(1)i(in)2i(2ni)!

有了以上基本常识就可以上大招了

例题

CF449D

大意:
给出一个长度为n的序列 a 1 , a 2 . . . a n a_1,a_2...a_n a1,a2...an。求从中选择一个非空子集使得他们的按位与之和等于0的方案数

思路:
不考虑复杂度的话我们有一个非常套路的容斥做法。考虑性质Ai表示子集与之后第i位为1,那么我们的答案其实就是
∣ Ω − A 1 ⋃ A 2 . . . ⋃ A 20 ∣ = ∑ i = 0 20 ( − 1 ) i ∑ 1 ≤ j 1 < j 2 . . . < j i ≤ 20 ∣ A j 1 ⋃ A j 2 . . . A j i ∣ |\Omega -A_1\bigcup A_2...\bigcup A_{20}|=\sum_{i=0}^{20}(-1)^i\sum_{1\leq j_1 < j_2...<j_i \leq 20 }|A_{j_1}\bigcup A_{j_2}...A_{j_i}| ∣ΩA1A2...A20=i=020(1)i1j1<j2...<ji20Aj1Aj2...Aji
其中||符号就表示集合的大小

显然就可以状压枚举,这样的时间复杂度是 O ( n ∗ 1 e 6 ) O(n*1e6) O(n1e6),考虑优化。

注意到对于 ∣ A j 1 ⋃ A j 2 . . . A j i ∣ |A_{j_1}\bigcup A_{j_2}...A_{j_i}| Aj1Aj2...Aji,我们记满足对应所有性质的元素的个数为k,则该集合的大小就是 2 k − 1 2^k-1 2k1,那么什么元素会满足这些性质呢?就是二进制为其超集的元素呗,其价值就是1.

所以我们只要做一遍超集后缀和即可,时间复杂度来到 O ( 20 ∗ 1 e 6 ) O(20*1e6) O(201e6)

code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const ll N=1e5+10;
const ll mod=1e9+7;
ll n,cnt=0,a;
ll mas[N];
ll up=20;
ll vis[30];
ll dp[(1<<20)+10];
ll ksm(ll x,ll y)
{
    ll ans=1;
    while(y)
    {
        if(y&1) ans=ans*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return ans;
}
ll gt()
{
    ll tot=0;
    ll fl;
    for(int i=1;i<=n;++i)
    {
        fl=1;
        for(int j=0;j<up;++j)
        {
            if(!vis[j]) continue;
            if((mas[i]&(1<<j))==0)
            {
                fl=0;
                break;
            }
        }
        if(fl) tot++;
    }

    return ((ksm(2,tot)-1)%mod+mod)%mod;
}
void solve()
{
    cin>>n;
    for(int i=1;i<=n;++i) cin>>a,dp[a]++;
    for(int j=0;j<up;++j)
    {
        for(int i=0;i<(1<<up);++i)
        {
            if((i&(1<<j))==0) dp[i]+=dp[i^(1<<j)];
        }
    }
    ll ans=0;
    for(int s=0;s<(1<<up);++s)
    {
        cnt=0;
        for(int i=0;i<up;++i) if(s&(1<<i)) cnt++;
        if(cnt%2) ans=((ans-ksm(2,dp[s])+1)%mod+mod)%mod;
        else ans=((ans+ksm(2,dp[s])-1)%mod+mod)%mod;
    }
    cout<<ans<<endl;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

CF1799G

大意:
在这里插入图片描述

思路:
个人认为这道题还是很顶的

题目有两个限制:每个人要得到 c i c_i ci票,每个人不能投给自己组

然后这里就有一个很巧妙的转化:我们可以先将同一个组的人放在一起来看,这样就可以将第一个限制稍微弱化一些,最后我们再想办法处理组内的方案数

那么此时的问题如下:每一个组 i i i总共有 n u m i num_i numi人,总共需要 f i f_i fi票,组内的人不能投给自己组,求合法方案数

考虑生成函数处理

我们用 a i a_i ai来表示第 i i i组的变元。那么对于第 i i i组的每一个人来说,它能投给除了自己组外的任河组,所以它的贡献是 a 1 + a 2 + . . . + a i − 1 + a i + 1 + . . . + a n a_1+a_2+...+a_{i-1}+a_{i+1}+...+a_n a1+a2+...+ai1+ai+1+...+an,我们可以简单记为 s − a i s-a_i sai,其中s就表示 ∑ i = 1 n a i \sum_{i=1}^{n}a_i i=1nai

那么我们最后得到式子为 ( s − a 1 ) n u m 1 ( s − a 2 ) n u m 2 . . . ( s − a n ) n u m n (s-a_1)^{num_1}(s-a_2)^{num_2}...(s-a_n)^{num_n} (sa1)num1(sa2)num2...(san)numn,记为 S S S,而我们的答案显然就是 [ a 1 f 1 a 2 f 2 . . . a n f n ] ( S ) [a_1^{f_1}a_2^{f_2}...a_n^{f_n}](S) [a1f1a2f2...anfn](S).此时不难发现,对于 a i a_i ai的指数,每一个s都可以提供1,而 ( s − a i ) n u m i (s-a_i)^{num_i} (sai)numi中的 − a i -a_i ai也可以提供不多于 n u m i num_i numi的指数。

所以我们考虑每一个 a i a_i ai的次数 det ⁡ i ( d e t i ≤ n u m i , d e t i ≤ f i ) \det_i(det_i \leq num_i,det_i \leq f_i) deti(detinumi,detifi),则每一个i有一个从 n u m i num_i numi中选择 d e t i det_i deti的方案数 ( n u m i d e t i ) \binom{num_i}{det_i} (detinumi),并且 d e t i det_i deti会提供 ( − 1 ) d e t i (-1)^{det_i} (1)deti的系数,然后剩下的所有指数都由 s s s提供,总共是 ∑ f i − ∑ d e t i = n − ∑ d e t i \sum f_i-\sum det_i=n-\sum det_i fideti=ndeti,要分成若干堆,第i堆有 f i − d e t i f_i-det_i fideti个,所以其实是一个可重集,不同组之间是相乘的关系,那么最终的答案其实就是
a n s = ∑ d e t i ≤ f i ( − 1 ) ∑ d e t i ∏ ( ( n u m i d e t i ) ) ( ( n − ∑ d e t i ) ! ( f 1 − d e t 1 ) ! ( f 2 − d e t 2 ) ! . . . ( f n − d e t n ) ! ) ans=\sum_{det_i\leq f_i}(-1)^{\sum det_i}\prod (\binom{num_i}{det_i})\binom{(n-\sum det_i)!}{(f_1-det_1)!(f_2-det_2)!...(f_n-det_n)!} ans=detifi(1)deti((detinumi))((f1det1)!(f2det2)!...(fndetn)!(ndeti)!)
= ∏ n u m i ∗ ∑ d e t i ≤ f i ( − 1 ) ∑ d e t i ( n − ∑ d e t i ) ! ∏ d e t i ! ( n u m i − d e t i ) ! ( f i − d e t i ) ! =\prod num_i *\sum_{det_i\leq f_i}(-1)^{\sum det_i}\frac{(n-\sum det_i)!}{\prod det_i!(num_i-det_i)!(f_i-det_i)!} =numidetifi(1)detideti!(numideti)!(fideti)!(ndeti)!

那么其实n只有200,所以我们可以比较轻松地来得到这个式子的结果

考虑枚举 ∑ d e t i \sum det_i deti,我们记为 d d d,那么再记一个 d p i , j dp_{i,j} dpi,j表示当前处理到了第i组, ∑ x ≤ i d e t i = j \sum_{x \leq i}det_i=j xideti=j,显然只要在过程中枚举合法的 d e t i det_i deti就能完成这个dp了,外层枚举d,内层枚举i,j,最内层枚举 d e t i det_i deti,乍一看时间复杂度好像是 O ( n 4 ) O(n^4) O(n4),但是因为 d e t i ≤ n u m i det_i \leq num_i detinumi,而 ∑ n u m i = n \sum num_i=n numi=n,所以实际复杂度只有 O ( n 3 ) O(n^3) O(n3)

这样我们就完成了组与组之间的关系。考虑组内部的票数分配, n u m i num_i numi个人,每一个人需要 c i c_i ci票,总共 ∑ c i = f i \sum c_i=f_i ci=fi票,所以这其实还是一个多重集,那么我们只要乘上系数 f i ! ∏ c i ! \frac{f_i!}{\prod c_i!} ci!fi!即可

推推式子还是有点累的~

code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const ll N=210;
const ll mod=998244353;
ll n;
ll f[N],t[N],c[N],num[N];//每一组的总期望票数,组别,个人期望票数,每组人数
ll dp[N][N];
ll ksm(ll x,ll y)
{
    ll ans=1;
    while(y)
    {
        if(y&1) ans=ans*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return ans;
}
ll inv(ll x)
{
    return ksm(x,mod-2);
}
ll p[N],pp[N];
void init(ll n)
{
    p[0]=1;
    for(ll i=1;i<=n;++i) p[i]=p[i-1]*i%mod;
    pp[n]=inv(p[n]);
    for(int i=n-1;i>=0;--i) pp[i]=pp[i+1]*(i+1)%mod;

}
void solve()
{
    init(200);
    // for(int i=1;i<=10;++i) cout<<p[i]<<" "<<pp[i]<<endl;
    cin>>n;
    for(int i=1;i<=n;++i) cin>>c[i];//期望票数
    for(int i=1;i<=n;++i) cin>>t[i],f[t[i]]+=c[i];
    for(int i=1;i<=n;++i) num[t[i]]++;
    ll ans=1,sum=0;
    for(int i=1;i<=n;++i) ans=ans*p[num[i]]%mod;
    
    for(int d=0;d<=n;++d)//det_i之和
    {
        for(int i=1;i<=n;++i) for(int j=0;j<=n;++j) dp[i][j]=0;
        dp[0][0]=p[n-d];

        for(int i=1;i<=n;++i)
        {
            //当前枚举到第i组
            for(int j=0;j<=d;++j)//到第i个人位置det_i的总和为j
            {
                for(int k=0;k<=min(f[i],num[i])&&k<=j;++k)//det_i=k
                {
                    ll det=pp[k]*pp[num[i]-k]%mod*pp[f[i]-k]%mod;
                    dp[i][j]=(dp[i][j]+det*dp[i-1][j-k]%mod)%mod;
                }
            }
        }
        if((d%2)==0) sum=(sum+ans*dp[n][d]%mod)%mod;
        else sum=((sum-ans*dp[n][d]%mod)%mod+mod)%mod;
    }
    for(int i=1;i<=n;++i)//组内多重集
    {
        sum=sum*p[f[i]]%mod*pp[c[i]]%mod;
    }
    cout<<sum<<endl;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

未完待续

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/54802.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

windows如何上架ios应用到app store

Application Uploader iOS App上架工具是一款非常好用的针对iOS苹果应用程序软件开发的实用编程工具&#xff0c;它的主要作用是帮助用户进行快速的程序应用设计和程序应用调试&#xff0c;节省用户进行软件开发耗费的不必要时间&#xff01; ​ 编辑切换为居中 添加图片注释&…

Minecraft 1.20.x Forge模组开发 05.矿石生成

我们本次尝试在主世界生成模组中自定义的矿石 效果演示 效果演示 效果演示 1.由于1.20的版本出现了深板岩层的矿石,我们要在BlockInit类中声明一个矿石的两种岩层形态: BlockInit.java package com.joy187.re8joymod.init;import java.util.function.Function;import java…

数据可视化(5)热力图及箱型图

1.热力图 #基本热力图 #imshow&#xff08;x&#xff09; #x&#xff0c;数据 x[[1,2],[3,4],[5,6],[7,8],[9,10]] plt.imshow(x) plt.show() #使用热力图分析学生的成绩 dfpd.read_excel(学生成绩表.xlsx) #:表示行号 截取数学到英语的列数 xdf.loc[:,"数学":英语].…

操作系统专栏2-文件系统from小林coding

文件系统 文件系统构成虚拟文件系统文件的使用文件的存储连续存储非连续空间存放方式链表方式索引方式 Linux文件的实现方式 空闲分区的管理文件系统结构目录的存储软链接和硬链接 文件系统构成 Linux的设计哲学有一点很重要:一切皆文件,不仅仅是普通的文件和目录,就连块设备,…

六、代理模式

文章目录 一、代理模式1、代理模式的好处和缺点1.1 代理模式理解加深 一、代理模式 为什么要学习代理模式&#xff1f; 代理模式是Spring AOP 以及 Spring MVC 的底层&#xff01;&#xff01;并且还是 JAVA 的23种设计模式之一&#xff01;&#xff01; 代理模式的分类&#…

C++ | 哈希表的实现与unordered_set/unordered_map的封装

目录 前言 一、哈希 1、哈希的概念 2、哈希函数 &#xff08;1&#xff09;直接定址法 &#xff08;2&#xff09;除留余数法 &#xff08;3&#xff09;平方取中法&#xff08;了解&#xff09; &#xff08;4&#xff09;随机数法&#xff08;了解&#xff09; 3、哈…

Nginx解决文件服务器文件名显示不全的问题

Nginx可以搭建Http文件服务器&#xff0c;但默认的搭建会长文件名显示不全&#xff0c;比如如下&#xff1a; 问题&#xff1a;显示不全&#xff0c;出现...&#xff0c;需要进行解决 这里使用重新编绎nginx的方式&#xff0c;见此文&#xff1a; https://unix.stackexchange…

刷题笔记 day4

力扣 611 有效三角形的个数 首先需要知道如何判断 三个数是否能构成三角形。 假如 存在三个数 a < b < c&#xff0c;如果要构成三角形&#xff0c;需要满足&#xff1a; ab > c ; a c > b ; b c > a ; 任意两个数大于第三个数就可构成三角形。 其实不难…

网络编程 IO多路复用 [select版] (TCP网络聊天室)

//head.h 头文件 //TcpGrpSer.c 服务器端 //TcpGrpUsr.c 客户端 select函数 功能&#xff1a;阻塞函数&#xff0c;让内核去监测集合中的文件描述符是否准备就绪&#xff0c;若准备就绪则解除阻塞。 原型&#xff1a; #include <sys/select.…

Codeforces Round 889 (Div. 2)(视频讲解A——D)

文章目录 A Dalton the TeacherB Longest Divisors IntervalC2 Dual (hard Version)D Earn or Unlock Codeforces Round 889 (Div. 2)&#xff08;视频讲解A——D&#xff09; A Dalton the Teacher #include<bits/stdc.h> #define endl \n #define INF 0x3f3f3f3f us…

设计模式大白话——装饰者模式

装饰者模式 文章目录 装饰者模式一、概述二、应用场景三、代码示例四、小结 一、概述 ​ 装饰者模式&#xff0c;此模式最核心之处在于装饰二字&#xff0c;之所以需要装饰&#xff0c;是因为基础的功能无法满足需求&#xff0c;并且装饰是临时的&#xff0c;并不是永久的&…

idea调节文字大小、日志颜色、git改动信息

idea调节菜单栏文字大小&#xff1a; 调节代码文字大小&#xff1a; 按住ctrl滚动滑轮可以调节代码文字大小&#xff1a; 单击文件即可在主窗口上打开显示&#xff1a; idea在控制台对不同级别的日志打印不同颜色 &#xff1a; “grep console”插件 点击某一行的时候&#x…

二叉树(C语言)

文章目录 1.树1.1概念1.2相关定义1.3 表示&#xff08;左孩子右兄弟&#xff09; 2.二叉树2.1概念2.2特殊的二叉树1. 满二叉树&#xff1a;2. 完全二叉树&#xff1a; 2.3二叉树的性质2.4练习 3.二叉树的存储结构1. 顺序存储2. 链式存储 4.完全二叉树的代码实现4.1堆的介绍1.堆…

Java+SpringBoot+Mybaties-plus+Vue+ElementUI 基于协同过滤算法商品推荐系统

一.项目介绍 协同过滤算法商品推荐系统分为两类角色 普通用户以及超级管理员 普通用户&#xff1a; 查看推荐商品、加入购物车、收藏、评论、个人中心、查看订单状态、编辑收货地址 超级管理员&#xff1a; 维护个人信息、维护用户管理、维护商品类型管…

解决构建maven工程时,配置了阿里云的前提下,依旧使用中央仓库下载依赖导致失败的问题!!!

问题描述&#xff1a; 在使用spring进行构建项目时&#xff0c;出现下载依赖迟迟不成功&#xff0c;显示maven wrapper 下载失败的问题。 Maven wrapper Cannot download ZIP distribution from https://repo.maven.apache.org/maven2/org/apache/maven/apache-maven/3.8.7/ap…

【Linux命令200例】patch 用于将补丁文件应用到源码中

&#x1f3c6;作者简介&#xff0c;黑夜开发者&#xff0c;全栈领域新星创作者✌&#xff0c;阿里云社区专家博主&#xff0c;2023年6月csdn上海赛道top4。 &#x1f3c6;本文已收录于专栏&#xff1a;Linux命令大全。 &#x1f3c6;本专栏我们会通过具体的系统的命令讲解加上鲜…

如何用python画一朵花,用python画彩色六边形

大家好&#xff0c;小编为大家解答用python画彩色六边形的问题。很多人还不知道如何用python画一朵花&#xff0c;现在让我们一起来看看吧&#xff01;

linux 学成之路(基础篇)(二十三)MySQL服务(下)

目录 一、用户权限管理概述 二、用户权限类型 三、用户赋予权限 四、删除权限 五、删除用户 一、用户权限管理概述 数据库用户权限管理是数据库系统中非常重要的一个方面&#xff0c;它用于控制不同用户访问和操作数据库的权限范围。数据库用户权限管理可以保护敏感数据和…

【phaser微信抖音小游戏开发004】往画布上增加文本以及文本的操作

我们在states中创建st004.js的类&#xff0c;或者将states中的index.js直接重命名为st004.js&#xff0c;把里面的类名也修改为st004.如下图 在main.js中&#xff0c;引入st004,并设置启用的state为st004。如下图 接下来到states/st004里面&#xff0c;在create里面将文本修改一…

Rust ESP32C3开发

Rust ESP32C3开发 系统开发逐步使用Rust语言&#xff0c;在嵌入式领域Rust也逐步完善&#xff0c;本着学习Rust和ESP32的目的&#xff0c;搭建了ESP32C3的环境&#xff0c;过程中遇到了不少问题&#xff0c;予以记录。 ESP-IDF开发ESP32 这一部分可跳过&#xff0c;是使用C开…