组合数学容斥原理答案_容斥原理例题精讲

组合数学容斥原理答案_容斥原理例题精讲一.容斥原理就是人们为了不重复计算重叠部分,想出的一种不重复计算的方法。先来认识一下这两个符号:与(如图)蓝色的圈就是c1c2,红色的圈围起来的就是c1c2二.例题:组合数学1.题目1.1.题目描述八是个很有趣的数字啊。八=发,八八=爸爸,88=拜拜。当然最有趣的还是8用二进制表示是1000。怎么样,有趣吧。当然题目和这些都没有关系。某个人很无聊,他想找出[a,b…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

一.容斥原理

就是人们为了不重复计算重叠部分,想出的一种不重复计算的方法。

先来认识一下这两个符号:\bigcap\bigcup(如图)

组合数学容斥原理答案_容斥原理例题精讲

蓝色的圈就是c1\bigcapc2,红色的圈围起来的就是c1\bigcupc2

二.例题:组合数学

1.题目

1.1.题目描述

八是个很有趣的数字啊。八=发,八八=爸爸,88=拜拜。当然最有趣的还是8用二进制表示是1000。怎么样,有趣吧。当然题目和这些都没有关系。 某个人很无聊,他想找出[a,b]中能被8整除却不能被其他一些数整除的数。

1.2.输入

第一行一个数n,代表不能被整除的数的个数。 第二行n个数,中间用空格隔开。 第三行两个数a,b,中间一个空格。 a < =b < =1000000000

1.3.输出

一个整数,为[a,b]间能被8整除却不能被那n个数整除的数的个数。

1.4.样例输入

3

7764 6082 462

2166 53442

1.5.样例输出

6378

1.6.提示

对于30%的数据, 1 ≤n ≤5,1 ≤a ≤ b ≤ 100000。
对于100%的数据,1 ≤ n ≤15,1 ≤ a ≤ b ≤ 10^9,N个数全都小于等于10000大于等于1。

 2.思路

这道题一看就是用容斥原理做吧,如果我们用ans表示答案,用B表示a到b的范围内可以被8整除的所有数,用E表示a到b范围内的所有数,Ai表示那n个要求不能整除的数,可以想到公式:

ans=B\bigcap (E-A_{1}\bigcup A_{2}\bigcup A_{3}\bigcup......\bigcup A_{n} )

它的意义就是:所有范围内的数减去所有能被那n个数整除的数与所有范围内能被8整除的数的并集

好,那么我们现在的问题就是如何求这些并集。(注意求两个数的并集就是求两个数的最小公倍数)

先举一个例子:假如有两个要求不被整除的数(如图,那两个数分别为1号圈和2号圈):

组合数学容斥原理答案_容斥原理例题精讲

那么,ans=8-8\bigcap 1+8\bigcap 1\bigcap 2-8\bigcap 2也就是:ans=8-①-②+②-②-③ 

再来一个稍复杂的:

组合数学容斥原理答案_容斥原理例题精讲

继续像例子1这样推:

ans=8-8\bigcap 6082+ 8\bigcap 6082\bigcap 462-8\bigcap 6082\bigcap 462\bigcap 7764+8\bigcap 6082\bigcap 7764-8\bigcap 462+8\bigcap 462\bigcap 7764-8\bigcap 7764

说人话,就是:ans=8-(①+⑤+④+②)+(②+④)-(④)+(④+⑤) -(③+②+④)+(④) -(④+⑤+⑥) 

可化简为:ans=8-①-②-④-③-⑤-⑥,就是我们想要求的答案了。大家可以发现,我打了下划线的部分是各个完整的部分,分别是8与其他数分别第一次并集

组合数学容斥原理答案_容斥原理例题精讲

然后8与这个数并集之后,又依次与其他的数继续并集,并且不重不漏,还有,在一个完整的部分里第奇数次并集相减,第偶数次相加,如:ans=8-(①+⑤+④+②)+(②+④)-(④)+(④+⑤) -(③+②+④)+(④) -(④+⑤+⑥) 

从8的集合开始,第0次加上8的集合内的所有数,到8\bigcap 6082开始第1次-(①+⑤+④+②)相减,第2次(②+④)相加,然后发现不能再并下去了,又回到8\bigcap 6082,开始新的第1次-(),第2次(④+⑤),发现也不能再走下去了,就到了8\bigcap 462,继续走下去就走完了。所以,这就是一个递归进行的过程,一个深搜就完事了。

void dfs (int k, int Index, LL v){//k代表第几次并集,Index代表到了第几个集合,v代表这个集合,如v=8,就代表8的倍数这个集合
    if (v > b)//超出范围就没有意义
        return ;
    if (k % 2 == 0)//第偶数次加,第基数次减
        ans += b / v - a / v;
    else
        ans -= b / v - a / v;
    for (int i = Index + 1; i <= n; i ++){
        LL t = lcm (v, m[i]);//求着两个集合的并集
        dfs (k + 1, i, t);//递归求解
    }
}

Jetbrains全家桶1年46,售后保障稳定

3.代码

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define LL long long
int n, m[130], a, b;
LL ans;
LL gcd (LL a, LL b){//最大公因数
    if (! b)
        return a;
    return gcd (b, a % b);
}
LL lcm (LL a, LL b){//最小公倍数
    return a * b / gcd (a, b);
}
void dfs (int k, int Index, LL v){//k代表第几次并集,Index代表到了第几个集合,v代表这个集合,如v=8,就代表8的倍数这个集合
    if (v > b)//超出范围就没有意义
        return ;
    if (k % 2 == 0)//第偶数次加,第基数次减
        ans += b / v - a / v;
    else
        ans -= b / v - a / v;
    for (int i = Index + 1; i <= n; i ++){
        LL t = lcm (v, m[i]);//求着两个集合的并集
        dfs (k + 1, i, t);//递归求解
    }
}
int main (){
    scanf ("%d", &n);
    for (int i = 1; i <= n; i ++)
        scanf ("%d", &m[i]);
    scanf ("%d %d", &a, &b);
    dfs (0, 0, 8);//从第0次开始
    printf ("%lld\n", ans);
    return 0;
}

4.感想

这道题的深搜是最考验人的,有时候只要带一些例子进去算一下就豁然开朗了。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/219638.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • CGLib简单入门

    CGLib简单入门一、CGlib简介        CGlib是一个强大的,高性能,高质量的Code生成类库。它可以在运行期扩展Java类与实现Java接口。 当然这些实际的功能是asm所提供的,asm又是什么?Java字节码操控框架,具体是什么大家可以上网查一查,毕竟我们这里所要讨论的是cglib。cglib就是封装了asm,简化了asm的操作,实现了在运行期动态生成新的class。 可能大家还感觉不到它的

  • 三极管是如何导通的?「建议收藏」

    三极管是如何导通的?「建议收藏」作者:被吊打的学渣链接:https://www.zhihu.com/question/19998995/answer/311658942来源:知乎著作权归作者所有。商业转载请联系作者获得授权,非商业转

  • 2020美赛A题翻译

    2020美赛A题翻译对于一些生活在海洋里的物种,全球海洋温度影响它们栖息地的质量。当对于它们的后续繁衍来说温度改变太大的时候,这些物种就会迁徙去寻找新的栖息地去更好地安放当前和未来的生殖繁衍。一个例子就是美国缅因州的龙虾的种群,它缓慢地往加拿大北部迁徙,那六更低的温度提供一个合适的栖息地环境。这种地理上的人口转移可能会对那些依赖海洋生物稳定性的公司的生计造成严重的破坏。您的团队已被苏格兰北大西洋渔业…

  • 图片懒加载原理及实现(java懒加载原理)

    一,前置知识1,为什么要图片懒加载懒加载是一种对网页性能优化的方式,比如当访问一个页面的时候,优先显示可视区域的图片而不是一次性加载所有图片,当需要显示时,再发送图片请求,避免打开网页时加载过多资源。当一个网站的加载图片过多时就需要懒加载的协助,页面图片多时,在首次载入时一次性加载会耗费时间长,使用懒加载可以使页面加载速度快、减轻服务器的压力、节省流量。如下图:随着滚轮滚动,底部的图片会被不断地加载,从而显示在页面上,也就是说懒加载其实就是按需加载,当页面需要显示图片的时候才进行加载,否则不加载

  • 用Matlab筛选mirbase,一种基于miRBase数据库的无参的miRNA数据分析方法与流程

    用Matlab筛选mirbase,一种基于miRBase数据库的无参的miRNA数据分析方法与流程本发明涉及转录组测序领域,具体涉及一种在miRBase数据库中无本物种参考miRNA数据的miRNA测序的数据分析方法。背景技术:miRNA是一类由内源基因编码非编码单链RNA分子,在动植物中参与转录后基因表达调控。多数miRNA以单拷贝、多拷贝或基因簇的形式存在于基因组中。miRNA在很多物种中被广泛发现,且在进化进程中高度保守,因此研究miRNA的确切功能、目的靶基因、以及其作用机制,是转录组…

    2022年10月25日
  • 硬件工程师成长之路(1)——元件基础「建议收藏」

    硬件工程师成长之路(1)——元件基础「建议收藏」送给大学毕业后找不到奋斗方向的你(每周不定时更新)

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号