#P12677. [集训队互测2025day10]分治

    ID: 11863 传统题 4000ms 512MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3300NOI/NOI+/CTS交换论证贡献法数位 DP计数 DP容斥原理交换求和顺序根号分治一维前缀和阶乘逆元预处理

[集训队互测2025day10]分治

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

Divide(l, r):
    Solve(l, r)
    if l = r: return
    mid = floor((l + r) / 2)
    Divide(l, mid)
    Divide(mid + 1, r)

Divide(1, n)

原伪代码图

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

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

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

输入格式

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

输出格式

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

样例输入

111

样例输出

17

样例解释

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

子任务

对于所有测试数据,1≤n<22000001 \le n < 2^{200000}。

下表保留原比赛的子任务说明。

子任务编号$n <$特殊限制分值
18无 10
212810
326214420
4$2^{200}$A5
5无5
6$2^{2000}$A5
7无10
8$2^{200000}$A10
9无25

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

原赛题(QOJ 9614)