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…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】
微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...
C++.OpenGL (10/64)基础光照(Basic Lighting)
基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...
C# SqlSugar:依赖注入与仓储模式实践
C# SqlSugar:依赖注入与仓储模式实践 在 C# 的应用开发中,数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护,许多开发者会选择成熟的 ORM(对象关系映射)框架,SqlSugar 就是其中备受…...

中医有效性探讨
文章目录 西医是如何发展到以生物化学为药理基础的现代医学?传统医学奠基期(远古 - 17 世纪)近代医学转型期(17 世纪 - 19 世纪末)现代医学成熟期(20世纪至今) 中医的源远流长和一脉相承远古至…...
Linux离线(zip方式)安装docker
目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1:修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本:CentOS 7 64位 内核版本:3.10.0 相关命令: uname -rcat /etc/os-rele…...

算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...

C++:多态机制详解
目录 一. 多态的概念 1.静态多态(编译时多态) 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1).协变 2).析构函数的重写 5.override 和 final关键字 1&#…...