XOR Triangle

题意翻译

## 题目描述 给你一个数 $n$，问：有多少对数 $0\leq a,b,c \leq n$ 满足 $a \oplus b,b \oplus c,a \oplus c$ 。三个数字构成了一个非退化三角形，也就是两条短边之和大于第三边的长度。$\oplus$ 表示二进制下的异或操作。 ## 输入格式 一个数字 $n$，表示给定的 n 在二进制下的表示。 ## 输出格式 输出答案 mod 998244353。

题目描述

You are given a positive integer $ n $ . Since $ n $ may be very large, you are given its binary representation. You should compute the number of triples $ (a,b,c) $ with $ 0 \leq a,b,c \leq n $ such that $ a \oplus b $ , $ b \oplus c $ , and $ a \oplus c $ are the sides of a non-degenerate triangle. Here, $ \oplus $ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). You should output the answer modulo $ 998\,244\,353 $ . Three positive values $ x $ , $ y $ , and $ z $ are the sides of a non-degenerate triangle if and only if $ x+y>z $ , $ x+z>y $ , and $ y+z>x $ .

输入输出格式

输入格式

The first and only line contains the binary representation of an integer $ n $ ( $ 0 < n < 2^{200\,000} $ ) without leading zeros. For example, the string 10 is the binary representation of the number $ 2 $ , while the string 1010 represents the number $ 10 $ .

输出格式

Print one integer — the number of triples $ (a,b,c) $ satisfying the conditions described in the statement modulo $ 998\,244\,353 $ .

输入输出样例

输入样例 #1

101

输出样例 #1

12

输入样例 #2

1110

输出样例 #2

780

输入样例 #3

11011111101010010

输出样例 #3

141427753

说明

In the first test case, $ 101_2=5 $ . - The triple $ (a, b, c) = (0, 3, 5) $ is valid because $ (a\oplus b, b\oplus c, c\oplus a) = (3, 6, 5) $ are the sides of a non-degenerate triangle. - The triple $ (a, b, c) = (1, 2, 4) $ is valid because $ (a\oplus b, b\oplus c, c\oplus a) = (3, 6, 5) $ are the sides of a non-degenerate triangle. The $ 6 $ permutations of each of these two triples are all the valid triples, thus the answer is $ 12 $ . In the third test case, $ 11\,011\,111\,101\,010\,010_2=114\,514 $ . The full answer (before taking the modulo) is $ 1\,466\,408\,118\,808\,164 $ .

题目大意：
给定一个正整数 \( n \)，计算满足以下条件的数对三元组 \( (a, b, c) \) 的数量：\( 0 \leq a, b, c \leq n \)，且 \( a \oplus b \)，\( b \oplus c \)，\( a \oplus c \) 能构成一个非退化三角形的边长。其中 \( \oplus \) 表示二进制下的异或操作。输出答案模 \( 998\,244\,353 \)。

输入输出数据格式：
- 输入格式：第一行包含一个整数 \( n \) 的二进制表示（没有前导零）。
- 输出格式：输出一个整数，即满足条件的三元组 \( (a, b, c) \) 的数量模 \( 998\,244\,353 \)。题目大意： 给定一个正整数 \( n \)，计算满足以下条件的数对三元组 \( (a, b, c) \) 的数量：\( 0 \leq a, b, c \leq n \)，且 \( a \oplus b \)，\( b \oplus c \)，\( a \oplus c \) 能构成一个非退化三角形的边长。其中 \( \oplus \) 表示二进制下的异或操作。输出答案模 \( 998\,244\,353 \)。 输入输出数据格式： - 输入格式：第一行包含一个整数 \( n \) 的二进制表示（没有前导零）。 - 输出格式：输出一个整数，即满足条件的三元组 \( (a, b, c) \) 的数量模 \( 998\,244\,353 \)。