数学知识(四)(容斥原理、博弈论)

2024-02-22 19:36

本文主要是介绍数学知识(四)(容斥原理、博弈论),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、容斥原理

容斥原理公式

一共加或者减的式子个数

 

(一)利用容斥原理解决求能被质数整除的数的个数

890计算能被整除的数的个数

因为一共有2^n-1种选法,可以用位运算的方式枚举,对于得到的每一种选法,根据存在的数的个数判断前面是1还是-1。枚举到2^n-1的所有二进制数,判断每一位上的数是否是1,

最重要的转变是:将能被各个质数整除的集合看成一个个的集合。根据容斥原理,需要计算各个集合的组合方式的元素个数然后相加。在找组合方式的时候因为一共有2^n-1种,可以用m位的二进制数表示。如何计算一个一个组合的可以整除的个数。一位一位右移&1判断。

#include<bits/stdc++.h>
//890 求能被质数整除的数
using namespace std;
typedef long long LL;
const int N=20;
int n,m;
int p[N];
int main()
{cin>>n>>m;//读入所有的质数for(int i=0;i<m;i++)cin>>p[i];int res=0;//遍历所有二进制数for(int i=1;i<1<<m;i++){int cnt=0;int t=1;//遍历这个二进制数的所有位for(int j=0;j<m;j++){if(i>>j&1){//记录当前选择集合的个数cnt++;//并将集合元素相乘t*=p[j];//如果n一倍的t都装不了就breakif(t>n){t=-1;break;}}}if(t!=-1){if(cnt%2)res+=n/t;else res-=n/t;}}cout<<res<<endl;}

二、博弈论

891 先手是否先获胜

结论:

如果异或值不是0,先手可以拿一堆石子儿让拿之后状态变成必输。

异或不会产生1,只会消除1。

因为异或上x之后会ai一定会变小,也就是这一堆石子儿是可以让棋手拿的。最后剩余ai异或x。整个式子异或之后是0.也就是可以进行一次操作并得到一个对手必败的局面(不管对手怎么去拿异或之后都不为0)。也就是先手先胜利。

先手遇到的总不是0,后手遇到的总是0,最后后手败。

#include<bits/stdc++.h>
//891 Nim游戏
using namespace std;
typedef long long LL;
int main()
{int n;cin>>n;int res=0;while(n--){int x;cin>>x;res^=x;}if(res)puts("Yes");else puts("No");return 0;
}

三、sg函数

mex是某个点的出边指向的所有点的值(不再其中)的最小的自然数。

如果sg不为0,就说明有出边指向0

nim游戏和sg函数含义相似。每个结点的sg函数可以看做一个小石头堆。nim游戏中异或之后如果不等于0,可以找到ai,拿走ai-ai^x。最后得到的状态就是0。在sg中。如果异或之后的值非0,和nim一样,将其变成ai^x。因为 ai^x<ai.所以一定有一个出边指向ai^x成立,并且之后的状态变成0.

#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_set>
using namespace std;
const int N = 110, M = 10010;
int n, m;
int s[N], f[M];
int sg(int x)
{if (f[x] != -1) return f[x];unordered_set<int> S;for (int i = 0; i < m; i ++ ){int sum = s[i];if (x >= sum) S.insert(sg(x - sum));}for (int i = 0; ; i ++ )if (!S.count(i))return f[x] = i;
}int main()
{cin >> m;for (int i = 0; i < m; i ++ ) cin >> s[i];cin >> n;memset(f, -1, sizeof f);int res = 0;for (int i = 0; i < n; i ++ ){int x;cin >> x;res ^= sg(x);}if (res) puts("Yes");else puts("No");return 0;
}

这篇关于数学知识(四)(容斥原理、博弈论)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/736270

相关文章

Spring Security 单点登录与自动登录机制的实现原理

《SpringSecurity单点登录与自动登录机制的实现原理》本文探讨SpringSecurity实现单点登录(SSO)与自动登录机制,涵盖JWT跨系统认证、RememberMe持久化Token... 目录一、核心概念解析1.1 单点登录(SSO)1.2 自动登录(Remember Me)二、代码分析三、

在MySQL中实现冷热数据分离的方法及使用场景底层原理解析

《在MySQL中实现冷热数据分离的方法及使用场景底层原理解析》MySQL冷热数据分离通过分表/分区策略、数据归档和索引优化,将频繁访问的热数据与冷数据分开存储,提升查询效率并降低存储成本,适用于高并发... 目录实现冷热数据分离1. 分表策略2. 使用分区表3. 数据归档与迁移在mysql中实现冷热数据分

从原理到实战深入理解Java 断言assert

《从原理到实战深入理解Java断言assert》本文深入解析Java断言机制,涵盖语法、工作原理、启用方式及与异常的区别,推荐用于开发阶段的条件检查与状态验证,并强调生产环境应使用参数验证工具类替代... 目录深入理解 Java 断言(assert):从原理到实战引言:为什么需要断言?一、断言基础1.1 语

MySQL中的表连接原理分析

《MySQL中的表连接原理分析》:本文主要介绍MySQL中的表连接原理分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、背景2、环境3、表连接原理【1】驱动表和被驱动表【2】内连接【3】外连接【4编程】嵌套循环连接【5】join buffer4、总结1、背景

深度解析Spring AOP @Aspect 原理、实战与最佳实践教程

《深度解析SpringAOP@Aspect原理、实战与最佳实践教程》文章系统讲解了SpringAOP核心概念、实现方式及原理,涵盖横切关注点分离、代理机制(JDK/CGLIB)、切入点类型、性能... 目录1. @ASPect 核心概念1.1 AOP 编程范式1.2 @Aspect 关键特性2. 完整代码实

Java Stream的distinct去重原理分析

《JavaStream的distinct去重原理分析》Javastream中的distinct方法用于去除流中的重复元素,它返回一个包含过滤后唯一元素的新流,该方法会根据元素的hashcode和eq... 目录一、distinct 的基础用法与核心特性二、distinct 的底层实现原理1. 顺序流中的去重

Spring @Scheduled注解及工作原理

《Spring@Scheduled注解及工作原理》Spring的@Scheduled注解用于标记定时任务,无需额外库,需配置@EnableScheduling,设置fixedRate、fixedDe... 目录1.@Scheduled注解定义2.配置 @Scheduled2.1 开启定时任务支持2.2 创建

Spring Boot 实现 IP 限流的原理、实践与利弊解析

《SpringBoot实现IP限流的原理、实践与利弊解析》在SpringBoot中实现IP限流是一种简单而有效的方式来保障系统的稳定性和可用性,本文给大家介绍SpringBoot实现IP限... 目录一、引言二、IP 限流原理2.1 令牌桶算法2.2 漏桶算法三、使用场景3.1 防止恶意攻击3.2 控制资源

Python中使用uv创建环境及原理举例详解

《Python中使用uv创建环境及原理举例详解》uv是Astral团队开发的高性能Python工具,整合包管理、虚拟环境、Python版本控制等功能,:本文主要介绍Python中使用uv创建环境及... 目录一、uv工具简介核心特点:二、安装uv1. 通过pip安装2. 通过脚本安装验证安装:配置镜像源(可

Mysql的主从同步/复制的原理分析

《Mysql的主从同步/复制的原理分析》:本文主要介绍Mysql的主从同步/复制的原理分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录为什么要主从同步?mysql主从同步架构有哪些?Mysql主从复制的原理/整体流程级联复制架构为什么好?Mysql主从复制注意