Codeforces Round 810 (Div. 1) |
---|
Finished |
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.
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$$$.
101
12
1110
780
11011111101010010
141427753
In the first test case, $$$101_2=5$$$.
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$$$.
Name |
---|