分数: 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