#1872. 分治
分治
分治
题目描述
标题: 分治 - Problem - QOJ.ac
#9614. 分治
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。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
111
17
样例 2
1111101
422