ARC143 F Counting Subsets
2022/7/21 6:24:44
本文主要是介绍ARC143 F Counting Subsets,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
-
题意
给定正整数 \(n\),求有多少 \(\{1,2,\dots ,n\}\) 的子集 \(S\) 满足任意一个 \(1\) 到 \(n\) 到整数都能被表示成 \(S\) 的子集和,且方案数小于等于 \(2\)。
对 \(998244353\) 取模。
\(n\le 1500\)
-
题解
一看到这个,就想到 AHOI 的山河重整,但做法完全不同。
考虑用背包判定 \(S\) 合法性的过程,设背包的 \(\text{dp}\) 数组为 \(f\),从 \(0\) 开始。
每加入一个数相当于是将 \(f\) 平移若干位然后对位相加。
这启发我们考虑第一次出现有一个数方案数为 \(2\) 的情况,这相当于枚举第一个不是 \(2\) 的次幂的数,设为 \(a\)。
在加入 \(a\) 后,我们的 \(f\) 应该形如 \(a\) 个 \(1\),若干个 \(2\) ,\(a\) 个 \(1\)。
忽略首尾的 \(1\),我们发现接下来每次操作相当于把 \(f\) 复制一遍,并在两段中间插入一个长为 \(a\sim 2a\) 的连续段。
这是一个满二叉树结构,每个点为一个连续段,因此我们可以考虑再枚举这棵树总长度第一次大于等于 \(n\) 时的节点数。
注意到一个问题:我们只对 \(1\sim n\) 的数有所限制,大于 \(n\) 的数是无所谓的。
那么我们求的就不是合法树个数,而是每个合法情况下,\(n\) 和前面第一个 \(2\) 的距离和。
如果直接 \(\text{dp}\),每次加一个根,我可能只会一个复杂度很高的算法(如果有会的求指教)。
我们考虑继续枚举一个二叉树上的点 \(x\),满足恰好 \(\text{dfs}\) 序小于等于它的点的长度和大于等于 \(n\)。
这样我们就确定了每一层的点选的个数,逐层 \(\text{dp}\) 是容易的,最后算贡献需要一些分类讨论。
我们来算一下复杂度。
对于每一个 \(a\),我们枚举的点 \(x\) 的个数是 \(\Theta(n/a)\) 的,对于一个 \(x\),\(\text{dp}\) 复杂度是 \(\Theta(n\log \frac{n}{a})\) 的,总复杂度 \(\Theta(n^2\log^2 n)\)。
这篇关于ARC143 F Counting Subsets的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升
- 2024-05-08代码报错不用愁,CodeGeeX一键完成代码修复、错误解释的功能上线了!
- 2024-05-08今天开始程序员不用再发愁写commit message了,全部由CodeGeeX自动完成!