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

博弈论(奇偶考虑法)+计数+DP(判定转dp):CF838C

首先题目有博弈,先分析一波最优策略(步骤:分析性质)。

两个人,所以显然考虑奇偶考虑法+递归考虑。

首先删就是使子问题-1,重新排列是在当前子问题里的。

一个串的排列是有限的,所以这里就可以上奇偶考虑法。如果有偶数种串,则必然是后手先“被迫“进入子问题(要算上初始情况)

考虑假设法:我们可以先假设进入子问题:

  1. 必赢。先手进!
  2. 必死。偶串时后手被迫进入,先手胜!

我们的奇偶考虑法证明了串方案wei偶数时先手必胜了!

考虑奇数种时先手能不能赢,同样假设一下:

  1. 进去必赢。先手胜
  2. 进去必输。先手被迫进入,后手胜

现在先手就不能再这层耗了,只能进入下一层了。然后结合上面的结论,只能进入子问题种类数是奇数时先手才有机会。

然后好像就卡住了…

然后回到题目看一看,发现问种类数,考虑dp太早了,就先想下计数

假设每种字符出现次数为 a a a,那么就有 a n \frac a n na种串。然后我们现在这个是奇数。

考虑删掉一个变成什么,是 n ! ∏ a ! ( a − 1 ) ! \frac {n!} {\prod a! (a-1)!} a!(a1)!n!,我们现在希望这个是奇数。我们除一下发现上面要乘个 a n \frac a n na,则这个也要是奇数。

我们考虑我们还漏了什么条件, ∑ a = n \sum a=n a=n。奇偶的话就从二进制的角度推敲一下, n n n 的最低位1必然存在在其中一个 a a a 里,所以 a n \frac a n na 为奇数必然存在。

所以现在只和 n n n 的奇偶有关了。 n n n 偶先手必胜,否则必败。

剩下dp就很简单了。若 n n n 为奇数,我们要构造 a n \frac a n na 为偶数,考虑用全局-奇。

因为有 ∏ a ! ∣ n ! \prod a! | n! a!n!,所以 ∏ a ! \prod a! a! 的2的因子和 n ! n! n! 只能相同。考虑类似10,不能用1+1表示,只能用10+0表示。所以每个 a a a 必然是 n n n 的子集。同时 ∑ a = n \sum a=n a=n

然后dp维护下 1 ∏ a ! \frac 1{\prod a!} a!1 的和。

有个小优化,就是钦定当前lowbit必选,最后乘个阶乘即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 250010
//#define M
//#define mo
int mo; 
int pw(int a, int b) {int ans=1; while(b) {if(b&1) ans*=a; a*=a; b>>=1; ans%=mo; a%=mo; }return ans; 
}
int fac[N], inv[N], ifac[N]; 
void init(int n) {int i; for(i=fac[0]=1; i<=n; ++i) fac[i]=fac[i-1]*i%mo; ifac[n]=pw(fac[n], mo-2); for(i=n-1; i>=0; --i) ifac[i]=ifac[i+1]*(i+1)%mo; for(i=1; i<=n; ++i) inv[i]=ifac[i]*fac[i-1]%mo; 
}
int C(int n, int m) {if(m>n) return 0;return fac[n]*ifac[m]%mo*ifac[n-m]%mo; 
}
int n, m, i, j, k, T;
int f[27][N], s, t, ans; void Add(int &a, int b) {
//	a=(a+b)%mo; a+=b; if(a>=mo || a<=mo) a%=mo; 
}int dfs(int i, int s) {
//	printf("f[%lld][%lld] %lld\n", i, s, f[i][s]); if(f[i][s]!=-1) return f[i][s]; if(i==0 || s==0) return 0; f[i][s]=0; int j=s&-s, t; 
//	printf("====\n"); 
//	printf("%lld %lld\n", S, j); for(t=(s-j); ; t=(t-1)&(s-j)) {//ai=tAdd(f[i][s], dfs(i-1, s-j-t)*ifac[t+j]); if(!t) break;  }
//	printf("f[%lld][%lld]=%lld\n", i, s, f[i][s]); return f[i][s]; 
}signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
//	T=read();
//	while(T--) {
//
//	}n=read(); k=read(); mo=read(); init(n); if(n%2) return printf("%lld\n", pw(k, n)), 0; memset(f, -1, sizeof(f)); f[0][0]=1; 
//	for(i=1; i<=k; ++i) printf("%lld %lld %lld\n",  fac[n], f[i][0], fac[n]*f[i][0]%mo); for(i=1; i<=k; ++i) {
//		printf("dfs[%lld %lld]=%lld\n", i, 0, dfs(i, 0)); Add(ans, fac[n]*dfs(i, n)%mo*C(k, i)%mo*fac[i]%mo); }
//	printf("%lld\n", (ans%mo+mo)%mo); Add(ans, pw(k, n)-2*ans); printf("%lld", (ans%mo+mo)%mo); return 0;
}

相关文章:

博弈论(奇偶考虑法)+计数+DP(判定转dp):CF838C

首先题目有博弈&#xff0c;先分析一波最优策略&#xff08;步骤&#xff1a;分析性质&#xff09;。 两个人&#xff0c;所以显然考虑奇偶考虑法递归考虑。 首先删就是使子问题-1&#xff0c;重新排列是在当前子问题里的。 一个串的排列是有限的&#xff0c;所以这里就可以…...

郁金香2021年游戏辅助技术中级班(一)

郁金香2021年游戏辅助技术中级班&#xff08;一&#xff09; 用代码读取utf8名字字节数组搜索UTF-8字符串 用CE和xdbg分析对象名字从LUA函数的角度进行分析复习怪物名字偏移 用CE和xdbg分析对象数组认识虚函数表分析对象数组 分析对象数组链表部分链表的定义链表的数据在内存里…...

加密货币交易所偿付能力的零知识证明

如何检测下一个 FTX 和 Mt. Gox 加密货币交易所 FTX 的内爆导致数十亿客户资金流失&#xff0c;这是加密货币历史上交易所破产的最新例子。历史可以追溯到 2014 年&#xff0c;当时处理 70% 比特币交易的历史最悠久、规模最大的交易所 Mt. Gox 丢失了用户的 850,000 个比特币。…...

软考网络工程师防火墙配置考点总结

&#xff08;考试重点&#xff09; 一、访问控制列表 管理网络当中的数据流量&#xff0c;实现数据过滤的重要手段。可以在路由器、三层交换、二层交换和防火墙上实现。 隐藏规则&#xff1a;当前面的规则都匹配不上&#xff0c;华为默认允许&#xff0c;思科默认拒绝。 分…...

【IDEA】idea恢复pom.xml文件显示灰色并带有删除线

通过idea打开spring boot项目后&#xff0c;发现每个服务中的pom.xml文件显示灰色并带有删除线&#xff0c;下面为解决方案 问题截图 解决方案 打开file——settings——build,execution,deployment——Ignored Files&#xff0c;把pom.xml前面的复选框去掉&#xff0c;去掉之…...

Python数据分析之Excel

Openpyxl库 1、Openpyxl模块2、Excel写入2.1、新建2.2、添加数据2.3、单元格格式 3、Excel读取4、Excel的CRUD4.1、查4.2、改4.3、删 1、Openpyxl模块 Openpyxl是一个用于处理xlsx格式Excel表格文件的第三方python库&#xff0c;几乎支持Excel表格的所有操作 基本概念&#x…...

NISP证书是什么?NISP含金量如何呢?

一、NISP是什么 NISP证书是国家信息安全水平考试&#xff08;National Information Security Test Program&#xff0c;简称NISP&#xff09;&#xff0c;是由中国信息安全测评中心实施培养国家网络空间安全人才的项目。由国家网络空间安全人才培养基地运营/管理&#xff0c;并…...

操作系统备考学习 day6(2.3.2 - 2.3.4)

操作系统备考学习 day6 第二章 进程与线程2.3 同步与互斥2.3.2 实现临界区互斥的基本方法单标记法双标志先检查法双标志后检查法Peterson算法 进程互斥的硬件实现方法中断屏蔽方法TestAndSet指令Swap指令 2.3.3 互斥锁2.3.4 信号量整型信号量记录型信号量 第二章 进程与线程 2…...

家电行业 EDI:Miele EDI 需求分析

Miele是一家创立于1899年的德国公司&#xff0c;以其卓越的工程技术和不懈的创新精神而闻名于世。作为全球领先的家电制造商&#xff0c;Miele的经营范围覆盖了厨房、洗衣和清洁领域&#xff0c;致力于提供高品质、可持续和智能化的家电产品。公司的使命是为全球消费者创造更美…...

Android ConstraintLayout app:layout_constraintHorizontal_weight

Android ConstraintLayout app:layout_constraintHorizontal_weight <?xml version"1.0" encoding"utf-8"?> <androidx.constraintlayout.widget.ConstraintLayout xmlns:android"http://schemas.android.com/apk/res/android"xmlns:…...

FPGA行业应用一:LED控制器

什么是LED控制器 LED控制器已经有很多年头了&#xff0c;应该是上世纪90年代就开始有了。它的主要构成是&#xff1a; 1&#xff1a;视频信号源——如 电脑&#xff0c;机机&#xff0c;DVD&#xff0c;U盘等 2&#xff1a;视频处理器——通过 HDMI/DVI/网口接收来自视频源的…...

Pyspark读写csv,txt,json,xlsx,xml,avro等文件

1. Spark读写txt文件 读&#xff1a; df spark.read.text("/home/test/testTxt.txt").show() ------------- | value| ------------- | a,b,c,d| |123,345,789,5| |34,45,90,9878| -------------2. Spark读写csv文件 读&#xff1a; # 文件在hdfs上…...

LeetCode 接雨水 双指针

原题链接&#xff1a; 力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 题面&#xff1a; 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图&#xff0c;计算按此排列的柱子&#xff0c;下雨之后能接多少雨水。 示例 1&#xff1a; 输入&#xff1a…...

【Linux】【网络】传输层协议:UDP

文章目录 UDP 协议1. 面向数据报2. UDP 协议端格式3. UDP 的封装和解包4. UDP 的缓冲区 UDP 协议 UDP传输的过程类似于寄信。 无连接&#xff1a;知道对端的IP和端口号就直接进行传输&#xff0c;不需要建立连接。不可靠&#xff1a;没有确认机制&#xff0c;没有重传机制&am…...

数字音频工作站FL Studio 21中文版下载及电音编曲要用乐理吗 电音编曲步骤

FL Studio 21是一款强大的数字音频工作站&#xff08;DAW&#xff09;软件&#xff0c;为您提供一个完整的软件音乐制作环境。它是制作高质量的音乐、乐器、录音等的完整解决方案。该程序配备了各种工具和插件&#xff0c;帮助你创建专业的虚拟乐器&#xff0c;如贝斯、吉他、钢…...

金蝶云星空与旺店通·企业奇门对接集成其他出库查询打通创建其他出库单

金蝶云星空与旺店通企业奇门对接集成其他出库查询打通创建其他出库单 源系统:金蝶云星空 金蝶K/3Cloud&#xff08;金蝶云星空&#xff09;是移动互联网时代的新型ERP&#xff0c;是基于WEB2.0与云技术的新时代企业管理服务平台。金蝶K/3Cloud围绕着“生态、人人、体验”&#…...

Visual Studio 如何删除多余的空行,仅保留一行空行

1.CtrlH 打开替换窗口&#xff08;注意选择合适的查找范围&#xff09; VS2010: VS2017、VS2022: 2.复制下面正则表达式到上面的选择窗口&#xff1a; VS2010: ^(\s*)$\n\n VS2017: ^(\s*)$\n\n VS2022:^(\s*)$\n 3.下面的替换窗口皆写入 \n VS2010: \n VS2017: \n VS2022: \n …...

java spring cloud 企业电子招标采购系统源码:营造全面规范安全的电子招投标环境,促进招投标市场健康可持续发展

功能描述 1、门户管理&#xff1a;所有用户可在门户页面查看所有的公告信息及相关的通知信息。主要板块包含&#xff1a;招标公告、非招标公告、系统通知、政策法规。 2、立项管理&#xff1a;企业用户可对需要采购的项目进行立项申请&#xff0c;并提交审批&#xff0c;查看所…...

112. 路径总和

力扣题目链接(opens new window) 给定一个二叉树和一个目标和&#xff0c;判断该树中是否存在根节点到叶子节点的路径&#xff0c;这条路径上所有节点值相加等于目标和。 说明: 叶子节点是指没有子节点的节点。 示例: 给定如下二叉树&#xff0c;以及目标和 sum 22&#xf…...

国货疯抢流量,B站接连爆发800万播放实现破圈

近日&#xff0c;“79元商战”的消息洗刷全平台&#xff0c;众多国货品牌的“不容易”开始被越来越多的消费者注意到&#xff0c;消费者们自发性地开始重新审视真正做产品的国货品牌们&#xff0c;并为之全力支持。有网友笑称&#xff1a;这“泼天的富贵”终于落到了国货品牌的…...

(高阶) Redis 7 第14讲 数据统计分析 实战篇

面试题 存得进,取得出,反应快抖音电商商品评论:排序+展现+取前10条用户使用手机APP签到打卡:1天对应一系列用户签到记录,新浪微博/钉钉打卡,如何进行统计页面访问点击量:一个网页对应一系列的访问点击,淘宝网首页,多少人浏览首页公司系统上线后,UV、PV、DUV是什么亿级…...

SpringCloud nacos1.x.x版本升级到2.2.3版本并开启鉴权踩坑

近期由于服务器漏洞扫描&#xff0c;检测出nacos存在绕过登录鉴权漏洞&#xff0c;如图 需要进行升级并开启鉴权&#xff0c;就此次升级做下记录。 1.首先备份原来的nacos&#xff0c;导出配置文件作为备份&#xff1b; 2&#xff0c;从官网下载nacos-server-2.2.3.zip&#x…...

软件测试/测试开发丨探索AI与测试报告的完美结合,提升工作效率

简介 测试报告的主要目的是提供与测试结果相关的数据信息&#xff0c;以便项目团队、开发人员、管理层和其他相关方可以了解测试的结果&#xff0c;并做出基于这些结果的明确下一步的决策&#xff0c;以及下一个版本的改进方向。 通常一个测试报告会包含 测试执行情况问题汇…...

Ubuntu 设置开机自动执行脚本

1. 建立service文件 sudo vim /etc/systemd/system/redis-server.service2. redis service文件 [Unit] DescriptionAdvanced key-value store Afternetwork.target Documentationhttp://redis.io/documentation, man:redis-server(1)[Service] Typenotify ExecStart/usr/bin/…...

【笔记】Splay

【笔记】Splay 目录 简介右旋左旋 核心思想操作a. Splayb. 插入c. 删除 信息的维护例题AcWing 2437. SplayP3369 【模板】普通平衡树 简介 Splay 是一种平衡树&#xff0c;并且是一棵二叉搜索树&#xff08;BST&#xff09;。 它满足对于任意节点&#xff0c;都有左子树上任意…...

opencv英文识别tesseract-orc安装

文章目录 一、安装并保存所在路径二、配置环境变量1、打开高级设置2、配置环境变量三、修改tesseract.py文件中的路径,否则运行报错1、进入python所在的文件夹,找到Lib,site-packages2、搜索pytesseract3、打开py文件修改路径一、安装并保存所在路径 特别注意路径名中不能有…...

JNA封装C/C++动态库在flink内使用记录

概述 因为公司业务需求&#xff0c;需要将一部分原本已经用C/C写好的程序封装到flink内部使用。 操作系统 CentOS 7使用的技术和工具 flink 1.17.1 JDK 19.0.2 JNA 5.12.1 maven 3.9.4技术实现 利用JNA将C/C的程序封装到JAR包里面&#xff0c;然后结合flink依赖&#xff0…...

Android gradle dependency tree change(依赖树变化)监控实现

文章目录 前言基本原理执行流程diff 报告不同分支 merge 过来的 diff 报告同个分支产生的 merge 报告同个分支提交的 diff 报告 具体实现原理我们需要监控怎样的 Dendenpency 变化怎样获取 dependency Treeproject.configurations 方式./gradlew dependenciesAsciiDependencyRe…...

5个流程图模板网站,帮你轻松绘制专业流程图

在复杂的项目管理和团队协作中&#xff0c;流程图成为了一个必不可少的工具。从零开始创建流程图可能会很耗时&#xff0c;同时也需要一定的技能。使用模板可以让流程图方便制作又保持高颜值&#xff0c;降低制作的成本&#xff0c;一款模板众多、功能强大、具有丰富编辑工具的…...

【AI视野·今日Robot 机器人论文速览 第四十二期】Wed, 27 Sep 2023

AI视野今日CS.Robotics 机器人学论文速览 Wed, 27 Sep 2023 Totally 48 papers &#x1f449;上期速览✈更多精彩请移步主页 Interesting: &#x1f4da;***Tactile Estimation of Extrinsic Contact,基于触觉的外部接触估计与稳定放置 (from 三菱电机) Daily Robotics Pape…...