#PQJ1835x9614. QOJ 1835_9614

    ID: 2725 传统题 4000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:2024-2025 集训队互测分治构造

QOJ 1835_9614

标题: 分治 - Problem - QOJ.ac

#9614. 分治

Statistics

The problem was used in the following contests:

小 X 使用分治算法解决了一个序列问题,大致代码如下:

其中 Solve⁡(l,r) 的运算次数恰好为 mex⁡ a[l…r],即在 a[l…r] 中最小的未出现的非负整数。请注意,在上述伪代码流程中,实际上并不可能让 Solve⁡(l,r) 只运行这么多次,你可以认为小 X 经过了一些其他操作达成了这一点,本题中我们忽略这一部分。

小 X 统计了几组数据下的运算次数后,扬言该代码的时间复杂度是 O(n) 的。 作为一名撅世高手,你不这么认为。请你构造一个长度为 n 的非负整数序列 ai,最大化上述代码的运行次数,以击碎这个菜鸟美好的幻想!

为了保持一个撅世高手的神秘感,你不会告诉他这个序列 ai,你只需要告诉他最大运行次数对 998244353 取模后的结果即可。

输入格式

输入一行一个正整数 n。注意,为了选手方便,将以二进制的形式表示 n。

输出格式

输出一行一个非负整数,表示最大运行次数对 998244353 取模后的结果。

样例输入

111

样例输出

17

样例解释

有多个运行次数达到 17 的序列,其中一个为 {3,2,1,0,1,0,4}。可以证明没有运行次数更多的方案。

子任务

对于所有测试数据,1≤n<2200000。

设置了合理的子任务依赖。

子任务编号 n< 特殊限制 分值 1 8 无 10 2 128 10 3 262144 20 4 2200 A 5 5 无 5 6 22000 A 5 7 无 10 8 2200000 A 10 9 无 25

特殊性质 A: 存在整数 k 使得 n=2k。