← 返回题目列表

AtCoder · agc039_c

C. 用某物除以二

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

给定的是整数 N 和 X。对于每个整数 k 之间 0 和 X (含),找到以下问题的答案,然后计算所有这些答案的总和,取模 998244353.

  • 让我们对整数重复以下操作 k。运算:如果当前整数是奇数,则减去 1 并将其除以 2;否则,将其除以 2 并添加 2^{N-1} 到它。需要执行多少次操作才能完成 k 恢复到原来的值? (答案被认为是 0 if k 永远不会返回到其原始值。)

约束

  • 1 \leq N \leq 2\times 10^5
  • 0 \leq X < 2^N
  • X 以二进制形式给出,并且恰好具有 N 数字。 (如果 X 少于 N 数字,以前导零给出。)
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
X

输出

打印问题答案的总和 0 和 X (含),模数 998244353.


示例输入 1

3
111

示例输出 1

40

例如,对于 k=3,操作发生变化 k 如下: 1,0,4,6,7,3。因此,答案为 k=3 is 6.


示例输入 2

6
110101

示例输出 2

616

示例输入 3

30
001110011011011101010111011100

示例输出 3

549320998