当前位置: 首页 > news >正文

CF 850 C Arpa and a game with Mojtaba(爆搜优化SG)

CF 850 C. Arpa and a game with Mojtaba(爆搜优化SG)

Problem - C - Codeforces

Arpa and a game with Mojtaba - 洛谷

思路:显然对于每一种质因子来说操作都是独立的 , 因此可以考虑对于每一种质因子求当前质因子的SG , 然后考虑组合这些局面。

对于每一种质因子来说 , 问题转化成了 , 当前状态有 n 堆石子 ,数量最多一堆的石子数量为 m 个 , 每人每次可以选择[1 - m]中任意一个数 t , 然后把所有数量 大于等于 t 的石子堆拿走 t 个 , 先不能操作的失败 , 问先手获胜情况。

打表发现一点规律都没有 , 又考虑到每一个数分解质因数后的数量很少 , 考虑爆搜SG。

对于爆搜可以考虑两个剪枝

1. 首先对于任意一个状态 , 排序后状态本质上不变 , 因此可以用一个状态的最小字典序或最大字典序表示当前状态。这样方便记忆化搜索。

2. 0 对于状态是无意义的 , 因此可以边操作边把0删去

3. 对于记忆化搜索的 map 来说 , 访问值之前一定要判空!!!

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int INF = 9e9;
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;#define ull unsigned long long
#define lld long double
map<int , int>factor;int qmul(int a ,int b,int mod){//快速乘,防止数据溢出 int c = (lld) a / mod * b;int res = (ull) a * b - (ull) c * mod;return (res + mod) % mod;
}int qual(int x,int d,int p){int ans = 1;while(d){if(d & 1) ans = qmul(ans , x , p); x = qmul(x , x , p);d >>= 1;}return ans;
}int A[] = {2 , 325 , 9375 , 28178 , 450775 , 9780504 , 1795265022};//判断素数 
bool miRoben(int x){if(x < 3 || x % 2 == 0) return x == 2;int d = x - 1 , r = 0;while(d % 2 == 0){d /= 2;r += 1;}for(auto a : A){int v = qual(a,d,x);if(v == 1 || v == x - 1 || v == 0) continue;for(int i = 1 ; i <= r ; i ++){v = qmul(v , v , x);if(v == x - 1 && i != r){v = 1;break;}if(v == 1) return false;}if(v != 1)return false;//费马小定理检验 }return true;
}int Pollard_Rho(int x){int s = 0 , t = 0;int c = (int)rand() % (x - 1) + 1;int step = 0 , goal = 1;int val = 1;for(goal = 1;;goal <<= 1 , s = t , val = 1){for(step = 1 ; step <= goal ; step ++){t = (qmul(t , t , x) + c) % x;val = qmul(val , abs(t - s) , x);if(step % 127 == 0){int d = __gcd(val , x);if(d > 1) return d;}}int d = __gcd(val , x);if(d > 1) return d;}
}//分解质因子 
void find(int n){if(n == 1) return;if(miRoben(n)){factor[n] += 1;return;}int p = n;while(p == n) p = Pollard_Rho(n);find(p);find(n / p);
}map<int , vector<int>> mp;map<vector<int> , int> dp;// 爆搜剪枝
//剪枝 对于 3 1 2 和 3 2 1 这两个状态显然相同 , 考虑每个状态用最小状态表示
//0 显然是无用状态 ,删掉即可int sg(vector<int> now) {sort(now.begin() , now.end() , greater<int>()); while(!now.back()) now.pop_back();if(dp.find(now) != dp.end()) return dp[now];set<int>st;int n = now.size();int maxx = now[0];for(int i = 1 ; i <= maxx ; i ++) {vector<int>oth = now;for(int j = 0 ; j < n ; j ++) {if(oth[j] >= i) oth[j] -= i;}st.insert(sg(oth));}for(int i = 0 ; ; i ++) if(!st.count(i)) return dp[now] = i;
}void init() {factor.clear();
}int n;signed main(){IOScin >> n;for(int i = 1 ; i <= n ; i ++) {int now; cin >> now;init();find(now);for(auto [x , y] : factor) {mp[x].push_back(y);}}int res = 0;for(auto [x , y] : mp) {res ^= sg(y); }cout << ((res == 0) ? "Arpa" : "Mojtaba");return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

相关文章:

CF 850 C Arpa and a game with Mojtaba(爆搜优化SG)

CF 850 C. Arpa and a game with Mojtaba&#xff08;爆搜优化SG&#xff09; Problem - C - Codeforces Arpa and a game with Mojtaba - 洛谷 思路&#xff1a;显然对于每一种质因子来说操作都是独立的 &#xff0c; 因此可以考虑对于每一种质因子求当前质因子的SG &#…...

kafka分布式安装部署

1.集群规划 2.集群部署 官方下载地址&#xff1a;http://kafka.apache.org/downloads.html &#xff08;1&#xff09;上传并解压安装包 [zhangflink9wmwtivvjuibcd2e package]$ tar -zxvf kafka_2.12-3.3.1.tgz -C ../software/&#xff08;2&#xff09;修改解压后的文件…...

[云原生2.] Kurbernetes资源管理 ---- (陈述式资源管理方式)

文章目录 1. K8s管理资源的方法类别1.1 陈述式资源管理方式1.2 声明式资源管理方式1.3 GUI式资源管理方法 2. 陈述式资源管理方式2.1 命令行工具 ---- Kubelet2.1.1 简介2.1.2 特性2.1.3 kubelet拓展命令2.1.4 kubectl基本语法2.1.5 Kubectl工具的自动补全 2.2 k8s Service 的类…...

java:IDEA中的Scratches and Consoles

背景 IntelliJ IDEA中的Scratches and Consoles是一种临时的文件编辑环境&#xff0c;用于写一些文本内容或者代码片段。 其中&#xff0c;Scratch files拥有完整的运行和debug功能&#xff0c;这些文件需要指定编程语言类型并且指定后缀。 举例&#xff1a;调接口 可以看到…...

华为 Mate 60 Pro 拆解:陆制零件比率上升至47% | 百能云芯

近日&#xff0c;日经新闻联合研究公司Fomalhaut Techno Solutions对华为 Mate 60 Pro 进行了拆解&#xff0c;揭示了这款于8月发布的新型智能手机的成本结构。拆解结果显示&#xff0c;该手机的国产零部件比例达到了47%&#xff0c;相较于三年前的 Mate 40 Pro&#xff0c;提高…...

ZBrush 2024(三维数字雕刻软件)

ZBrush是一款Mac数字雕刻软件&#xff0c;它具有以下功能&#xff1a; 雕刻工具&#xff1a;ZBrush的雕刻工具非常强大&#xff0c;可以让用户在3D模型上进行雕刻&#xff0c;就像使用传统雕塑工具一样。高精度模型创建&#xff1a;ZBrush可以创建高精度的3D模型&#xff0c;适…...

wpf devexpress 排序、分组、过滤数据

这个教程示范在GridControl如何排序数据&#xff0c;分组数据给一个行创建一个过滤。这个教程基于前一个教程。 排序数据 可以使用GridControl 排序数据。这个例子如下过滤数据对于Order Date 和 Customer Id 行&#xff1a; 1、对于Order Date 和 Customer Id 行指定Colum…...

使用Badboy录制生成 JMeter 脚本

JMeter是一款在国外非常流行和受欢迎的开源性能测试工具&#xff0c;像LoadRunner 一样&#xff0c;它也提供了一个利用本地Proxy Server&#xff08;代理服务器&#xff09;来录制生成测试脚本的功能&#xff0c;但是这个功能并不好用。所以在本文中介绍一个更为常用的方法——…...

V10 桌面版、服务器版系统加固

V10 桌面版、服务器版系统加固 一、 文档说明 本文档中涉及的加固方法主要包括&#xff1a;密码策略配置、防火墙规 则配置、禁用高风险服务等。 二、 V10 桌面版系统加固 2.1 密码策略配置 密码策略包括密码老化控制策略和密码复杂度策略。密码老化 控制策略需要配置/etc…...

mtgsig1.2简单分析

{"a1": "1.2", # 加密版本"a2": new Date().valueOf() - serverTimeDiff, # 加密过程中用到的时间戳. 这次服主变坏了, 时间戳需要减去一个 serverTimeDiff(见a3) ! "a3": "这是把xxx信息加密后提交给服务器, 服主…...

场景交互与场景漫游-osgGA库(5)

osgGA库 osgGA库是OSG的一个附加的工具库&#xff0c;它为用户提供各种事件处理及操作处理。通过osgGA库读者可以像控制Windows窗口一样来处理各种事件 osgGA的事件处理器主要由两大部分组成&#xff0c;即事件适配器和动作适配器。osgGA:GUIEventHandler类主要提供了窗口系统的…...

Leetcode -1

Leetcode Leetcode -521.最长特殊序列Leetcode - 541.反转字符串Ⅱ Leetcode -521.最长特殊序列 题目&#xff1a;给你两个字符串 a 和 b&#xff0c;请返回 这两个字符串中 最长的特殊序列的长度。如果不存在&#xff0c;则返回 - 1 。 「最长特殊序列」 定义如下&#xff1…...

系列四、JVM的内存结构【本地接口(Native Interface)】

一、组成 本地接口由本地方法栈&#xff08;Native Method Stack&#xff09;、本地方法接口&#xff08;Native Interface&#xff09;、本地方法库组成。 二、本地接口的作用 本地接口的作用是融合不同的编程语言为Java所用&#xff0c;它的初衷是融合C/C程序&#xff0c;Jav…...

大型语言模型中的幻觉研究综述:原理、分类、挑战和未决问题11.15+11.16+11.17

大型语言模型中的幻觉研究综述&#xff1a;原理、分类、挑战和未决问题11.15 摘要1 引言2 定义2.1 LLM2.3 大语言模型中的幻觉 3 幻觉的原因3.1 数据的幻觉3.1.1 有缺陷的数据源3.1.2 较差的数据利用率3.1.3 摘要 3.2 来自训练的幻觉3.2.1训练前的幻觉3.2.2来自对齐的幻觉3.2.3…...

redis悲观锁和乐观锁

redis悲观锁 Redis加锁命令分有INCR、SETNX、SET 一、INCR锁 key不存在时&#xff0c;key的值会先被初始化为0&#xff0c;其它用户在执行INCR操作进行加一&#xff0c; 如果返回的数大于1&#xff0c;说明这个锁正在被使用当中&#xff0c;通常用在同时只能有一个人可以操作某…...

前端项目练习,首页退出登录功能,清除token --点击事件 quitFn

<el-menu-item index"2" click"quitFn"><i class"el-icon-switch-button">退出</i> </el-menu-item>quitFn() {// 为了让用户体验更好&#xff0c;来个确认提示框this.$confirm("确认退出登录吗&#xff1f;退出登…...

nodejs+vue杰和牧场管理系统的设计与实现-微信小程序-安卓-python-PHP-计算机毕业设计

系统涉及的对象是奶牛。 系统使用员工有管理员和普通员工。 管理员有修改的权限&#xff0c;普通员工没有。系统包含新闻功能&#xff0c;最好是有个后台管理&#xff0c;在后台输入新闻标题和内容&#xff0c;插入图片&#xff0c;在网页上就可以展示。最好再有个轮播图。 新闻…...

基于STM32的蓝牙低功耗(BLE)通信方案设计与实现

蓝牙低功耗&#xff08;Bluetooth Low Energy&#xff0c;简称BLE&#xff09;是一种能够在低功耗环境下实现无线通信的技术。在物联网应用中&#xff0c;BLE被广泛应用于传感器数据采集、健康监测设备、智能家居等领域。本文将基于STM32微控制器&#xff0c;设计并实现一个简单…...

qt 重载信号,使用““方式进行connect()调用解决方案

问题 在Qt中&#xff0c;重载的信号默认是无法使用&这种方式调用的。 因为&只能绑定到一个具体的信号&#xff0c;而重载的信号名称相同&#xff0c;编译器无法确定要绑定哪一个信号。 解决方案 如果非要使用&绑定重载的信号&#xff0c;可以使用函数指针进行转…...

阿里云+宝塔部署项目(Java+React)

阿里云服务器宝塔面板部署项目&#xff08;SpringBoot React&#xff09; 1. 上传所需的文件到服务器 比如jdk包和java项目的jar&#xff1a;这里以上传jar 为例&#xff0c;创建文件夹&#xff0c;上传文件&#xff1b; 在创建的文件夹下上传jar包 上传jdk 2. 配置jdk环境 3.…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...

MySQL JOIN 表过多的优化思路

当 MySQL 查询涉及大量表 JOIN 时&#xff0c;性能会显著下降。以下是优化思路和简易实现方法&#xff1a; 一、核心优化思路 减少 JOIN 数量 数据冗余&#xff1a;添加必要的冗余字段&#xff08;如订单表直接存储用户名&#xff09;合并表&#xff1a;将频繁关联的小表合并成…...

HubSpot推出与ChatGPT的深度集成引发兴奋与担忧

上周三&#xff0c;HubSpot宣布已构建与ChatGPT的深度集成&#xff0c;这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋&#xff0c;但同时也存在一些关于数据安全的担忧。 许多网络声音声称&#xff0c;这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...

针对药品仓库的效期管理问题,如何利用WMS系统“破局”

案例&#xff1a; 某医药分销企业&#xff0c;主要经营各类药品的批发与零售。由于药品的特殊性&#xff0c;效期管理至关重要&#xff0c;但该企业一直面临效期问题的困扰。在未使用WMS系统之前&#xff0c;其药品入库、存储、出库等环节的效期管理主要依赖人工记录与检查。库…...

flow_controllers

关键点&#xff1a; 流控制器类型&#xff1a; 同步&#xff08;Sync&#xff09;&#xff1a;发布操作会阻塞&#xff0c;直到数据被确认发送。异步&#xff08;Async&#xff09;&#xff1a;发布操作非阻塞&#xff0c;数据发送由后台线程处理。纯同步&#xff08;PureSync…...