← 返回题目列表

Codeforces · 1710/C

C. 异或三角形

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

给你一个正整数$$$n$$$。由于 $$$n$$$ 可能非常大,因此您将获得其二进制表示形式。

您应该使用 $$$0 \leq a,b,c \leq n$$$ 计算三元组 $$$(a,b,c)$$$ 的数量,使得 $$$a \oplus b$$$、$$$b \oplus c$$$ 和 $$$a \oplus c$$$ 是非退化三角形的边。

这里,$$$\oplus$$$ 表示按位异或运算。

您应该输出对 $$$998\,244\,353$$$ 取模的答案。

三个正值 $$$x$$$、$$$y$$$ 和 $$$z$$$ 是非退化三角形的边当且仅当 $$$x+y>z$$$、$$$x+z>y$$$ 和 $$$y+z>x$$$。

输入

第一行也是唯一一行包含整数 $$$n$$$ ($$$0 < n < 2^{200\,000}$$$) 的二进制表示形式,不带前导零。

例如,字符串 10 是数字 $$$2$$$ 的二进制表示,而字符串 1010 表示数字 $$$10$$$。

输出

打印一个整数 — 满足语句中描述的条件的三元组 $$$(a,b,c)$$$ 的数量以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

101

输出 #1

12

输入 #2

1110

输出 #2

780

输入 #3

11011111101010010

输出 #3

141427753

注意

在第一个测试用例中,$$$101_2=5$$$。

- 三元组 $$$(a, b, c) = (0, 3, 5)$$$ 有效,因为 $$$(a\oplus b, b\oplus c, c\oplus a) = (3, 6, 5)$$$ 是非退化三角形的边。
- 三元组 $$$(a, b, c) = (1, 2, 4)$$$ 有效,因为 $$$(a\oplus b, b\oplus c, c\oplus a) = (3, 6, 5)$$$ 是非退化三角形的边。

这两个三元组的 $$$6$$$ 排列都是有效的三元组,因此答案是 $$$12$$$。

在第三个测试用例中,$$$11\,011\,111\,101\,010\,010_2=114\,514$$$。完整答案(取模之前)是 $$$1\,466\,408\,118\,808\,164$$$。