CF1784D Wooden Spoon
CF1784D Wooden Spoon
题目大意
有2n2^n2n个人,进行nnn轮比赛。比赛的图是一棵完全二叉树。编号小的人一定能赢编号大的人,如果一个人满足:
- 第一次比赛被打败
- 打败这个人的人在第二次比赛中被打败
- 打败上一个人的人在第三次比赛中被打败
- …\dots…
- 打败上一个人的人在最后一次比赛中被打败
那么这个人就能得到安慰奖。
求对于每个人,有多少种编号的排列来比赛(叶子的排列),使得他能得安慰奖。输出答案模998244353998244353998244353。
题解
我们按照题意来构建这棵二叉树,叶子节点就是这个序列,而非叶子节点的权值就是其子树中权值最大的点的权值。假如编号为kkk的点能拿安慰奖,那么这个点到根的路径上的点的权值一定是单调递减的。
假设这个点到根的权值组成的序列为a0,a1…,ana_0,a_1\dots,a_na0,a1…,an,我们依次来看每个点的贡献。
aia_iai的贡献为C(2n−ai−2i−1,2i−1−1)×(2i−1)!C(2^n-a_i-2^{i-1},2^{i-1}-1)\times (2^{i-1})!C(2n−ai−2i−1,2i−1−1)×(2i−1)!。也就是说,这个点在没有kkk的那棵子树中还要放小于他的2i−1−12^{i-1}-12i−1−1个点。因为要小于aia_iai,而且自己是一定要选的,所以要减aia_iai。又因为有kkk的那一边的点不能选,所以要减2i−12^{i-1}2i−1。这棵子树内的点的顺序可以任意排列,所以要乘上(2i−1)!(2^{i-1})!(2i−1)!。
设fi,sf_{i,s}fi,s表示第iii个数为sss时第iii个数到第nnn个数的贡献,gi,sg_{i,s}gi,s表示第iii个数小于等于sss时第iii个数到第nnn个数的贡献和。那么转移式为
fi,s=gi+1,s−1×C(2n−s−2i−1,2i−1−1)×(2i−1)!f_{i,s}=g_{i+1,s-1}\times C(2^n-s-2^{i-1},2^{i-1}-1)\times (2^{i-1})!fi,s=gi+1,s−1×C(2n−s−2i−1,2i−1−1)×(2i−1)!
gi,s=gi,s−1+fi,sg_{i,s}=g_{i,s-1}+f_{i,s}gi,s=gi,s−1+fi,s
因为kkk的位置任意,所以最后还要乘上2n2^n2n。那么编号为kkk的点的答案就是g1,k−1×2ng_{1,k-1}\times 2^ng1,k−1×2n。
时间复杂度为O(n×2n)O(n\times 2^n)O(n×2n)。
code
#include<bits/stdc++.h>
using namespace std;
const int N=1<<20;
int n;
long long jc[N+5],ny[N+5];
long long f[25][N+5],g[25][N+5];
long long mod=998244353;
long long mi(long long t,long long v){if(!v) return 1;long long re=mi(t,v/2);re=re*re%mod;if(v&1) re=re*t%mod;return re;
}
void init(){jc[0]=1;for(int i=1;i<=N;i++) jc[i]=jc[i-1]*i%mod;ny[N]=mi(jc[N],mod-2);for(int i=N-1;i>=0;i--) ny[i]=ny[i+1]*(i+1)%mod;
}
long long C(int x,int y){if(x<y) return 0;return jc[x]*ny[y]%mod*ny[x-y]%mod;
}
int main()
{init();scanf("%d",&n);for(int s=1;s<=(1<<n);s++){f[n][s]=C((1<<n)-s-(1<<n-1),(1<<n-1)-1)*jc[1<<n-1]%mod;g[n][s]=(g[n][s-1]+f[n][s])%mod;}for(int i=n-1;i>=1;i--){for(int s=1;s<=(1<<n);s++){f[i][s]=g[i+1][s-1]*C((1<<n)-s-(1<<i-1),(1<<i-1)-1)%mod*jc[1<<i-1]%mod;g[i][s]=(g[i][s-1]+f[i][s])%mod;}}for(int s=1;s<=(1<<n);s++){printf("%lld\n",g[1][s-1]*(1<<n)%mod);}return 0;
}
相关文章:
CF1784D Wooden Spoon
CF1784D Wooden Spoon 题目大意 有2n2^n2n个人,进行nnn轮比赛。比赛的图是一棵完全二叉树。编号小的人一定能赢编号大的人,如果一个人满足: 第一次比赛被打败打败这个人的人在第二次比赛中被打败打败上一个人的人在第三次比赛中被打败…\d…...

【数据结构】栈
文章目录😺前言栈初始化栈顶入栈栈顶出栈栈体判空栈的数据个数获取栈顶元素栈的销毁整体代码😼写在最后😺前言 👻前面我们学习了链表,总算是跨过一个台阶了,本章带大家轻松一波,领悟一下栈的魅力…...

C++单继承和多继承
C单继承和多继承继承单继承写法继承中构造函数的写法写法构造和析构的顺序问题多继承继承 1.继承,主要是遗传学中的继承概念 2.继承的写法,继承中的权限问题 3.继承中的构造函数的写法 继承:子类没有新的属性,或者行为的产生 父类…...

金三银四,今年企业招聘如何?
又是一年求职季,互联网人找工作,和找对象一样严谨,不随便放手更不随便牵手。于是挑挑拣拣,最后的结果可能就是把自己挑剩下了。 时间已经悄然滑进3月中旬,多少无处安放的青春,还没尘埃落定?优秀…...
数字信号处理:滤波、频谱
一、滤波算法 应该说数字滤波器可以有效减小50Hz工频的干扰,完全消除是不可能的。以20ms为最小单位的整倍数周期滤波,可以有效减少工频的干扰。 软件中构建 IIR 陷波或者 FIR 带阻 数字滤波器,消除工频干扰对测量结果的影响。 1. 自适应滤波 …...

C#等高级语言运行过程
C#等高级语言运行流程:假设您编写了一个 C# 程序并将其保存在一个称为源代码的文件中。特定于语言的编译器将源代码编译成 MSIL(Microsoft 中间语言),也称为 CIL(通用中间语言)或 IL(中间语言&a…...

如何优雅的用POI导入Excel文件
在企业级项目开发中,要经常涉及excel文件和程序之间导入导出的业务要求,那么今天来讲一讲excel文件导入的实现。java实现对excel的操作有很多种方式,例如EasyExcel等,今天我们使用的是POI技术实现excel文件的导入。POI技术简介1.P…...

【AI 工具】文心一言内测记录
文章目录一、申请内测二、收到内测邀请三、激活内测四、开始使用1、普通对话2、生成图片3、生成代码4、写剧本5、生成小说五、问题反馈一、申请内测 到 https://yiyan.baidu.com/welcome 页面 , 点击 " 开始体验 " 按钮 , 申请试用 ; 申请时 , 需要填写相关信息 ; 主…...

Github的使用
Github Date: March 8, 2023 Sum: Github的使用 Github 了解开源相关的概念 1. 什么是开源 2. 什么是开源许可协议 开源并不意味着完全没有限制,为了限制使用者的使用范围和保护作者的权利,每个开源项目都应该遵守开源许可协议( Open Sou…...

抽丝剥茧还原真相,记一次神奇的崩溃
作者:靳倡荣 本文详细回放了一个崩溃案例的分析过程。回顾了C多态和类内存布局、pc指针与芯片异常处理、内存屏障的相关知识。 一、不讲“武德”的崩溃 1.1 查看崩溃调用栈 客户反馈了一个崩溃问题,并提供了core dump文件,查看崩溃调用栈如下…...

学习笔记八:docker资源配额
docker容器控制cpudocker容器控制cpu指定docker容器可以使用的cpu份额两个容器A、B的cpu份额分别为1000和500,结果会怎么样?给容器实例分配512权重的cpu使用份额总结CPU core核心控制扩展:服务器架构CPU配额控制参数的混合使用cpuset-cpus和c…...

小米10s格机修复 nv报错案例解析 关于基带分区的一些常识
前面分享过几期关于基带 diag端口与qcn相关的几篇帖子。其中一位粉丝朋友联系我。他的机型因为误格机导致手机进不去系统,反复进入官方rec报错nv损坏。进不去系统。 有兴趣的朋友可以参阅我的几个帖子,只是个人的一些片面理解。 基带相关贴; 安卓玩机…...

【3.17】MySQL索引整理、回溯(分割、子集问题)
3.1 索引常见面试题 索引的分类 什么是索引? 索引是一种数据结构,可以帮助MySQL快速定位到表中的数据。使用索引,可以大大提高查询的性能。 按「数据结构」分类:Btree索引、Hash索引、Full-text索引。 InnoDB 存储引擎创建的聚簇…...

转解疑难杂症,详解vector迭代器失效和深浅拷贝的问题
前文http://t.csdn.cn/kVeVX——vector模拟实现本篇文章主要是针对vector中的两个比较经典的问题同时也是上一篇文章遗留下来的问题进行详细解释,第一个就是迭代器失效的问题,第二个是深浅拷贝的问题。ps:注意本文演示用的代码是上一篇vector…...

质量工具之头脑风暴法
云质QMS原创 转载请注明来源 作者:王洪石 1. 什么是头脑风暴法 头脑风暴最早是精神病理学上的用语,指的是精神病患者的精神错乱状态,后来拓展为无限制的自由联想和讨论,其目的在于产生新创意、激发新设想,或通过找到新…...

【3】核心易中期刊推荐——人工智能计算机仿真
🚀🚀🚀NEW!!!核心易中期刊推荐栏目来啦 ~ 📚🍀 核心期刊在国内的应用范围非常广,核心期刊发表论文是国内很多作者晋升的硬性要求,并且在国内属于顶尖论文发表,具有很高的学术价值。在中文核心目录体系中,权威代表有CSSCI、CSCD和北大核心。其中,中文期刊的数…...

vFlash软件简介
🍅 我是蚂蚁小兵,专注于车载诊断领域,尤其擅长于对CANoe工具的使用🍅 寻找组织 ,答疑解惑,摸鱼聊天,博客源码,点击加入👉【相亲相爱一家人】🍅 玩转CANoe&…...

mysql-online-ddl是否需要rebuild
一、背景 DDL一直是DBA业务中的大项,看了TIDB的DDL讲解,恰巧我们的mysql业务大表也遇到了DDL的变更项,变更内容是将varchar(10)变更成varchar(20),这个变更通过官方文档很容易知道是不需要rebuild的(这里要注意下这个varchar(255…...

力扣-超过经理收入的员工
大家好,我是空空star,本篇带大家了解一道简单的力扣sql练习题。 文章目录前言一、题目:181. 超过经理收入的员工二、解题1.正确示范①提交SQL运行结果2.正确示范②提交SQL运行结果3.正确示范③提交SQL运行结果4.正确示范④提交SQL运行结果5.其…...
决策树基础知识点解读
目录 ID3算法 C4.5算法 CART树 ID3算法 定义:在决策树各个结点上应用信息增益准则选择特征,递归的构建决策树。该决策树是多分支分类。 信息增益 意义:给定特征X的条件下,使得类别Y的信息的不确定性减少的程度。取值越大越好。 定义&am…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...

MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建
制造业采购供应链管理是企业运营的核心环节,供应链协同管理在供应链上下游企业之间建立紧密的合作关系,通过信息共享、资源整合、业务协同等方式,实现供应链的全面管理和优化,提高供应链的效率和透明度,降低供应链的成…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)
概述 在 Swift 开发语言中,各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过,在涉及到多个子类派生于基类进行多态模拟的场景下,…...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...

基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...

跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
LLM基础1_语言模型如何处理文本
基于GitHub项目:https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken:OpenAI开发的专业"分词器" torch:Facebook开发的强力计算引擎,相当于超级计算器 理解词嵌入:给词语画"…...

基于TurtleBot3在Gazebo地图实现机器人远程控制
1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...
LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》
这段 Python 代码是一个完整的 知识库数据库操作模块,用于对本地知识库系统中的知识库进行增删改查(CRUD)操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 📘 一、整体功能概述 该模块…...