XOR Triangle
Contest: Codeforces Round 810 (Div. 1)
Difficulty rating: 2500
Tags: bitmasks, brute force, constructive algorithms, dp, greedy, math

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$$$.

Input format:
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$$$.

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

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
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$$$.

Example input:
101

Example output:
12

Example input:
1110

Example output:
780

Editorial:
## Rhodoks's solution:
Define $$$cnt_{i_1 i_2 i_3}$$$ as:
$$$j$$$th bit of $$$cnt_{i_1 i_2 i_3}$$$ is $$$1$$$ iif $$$i_1=a_j,i_2=b_j,i_3=c_j$$$
e.g. $$$a=(10)_2,b=(11)_2,c=(01)_2$$$ then $$$cnt_{110}=(10)_2,cnt_{011}=(01)_2$$$, other $$$cnt$$$ is 0.
$$$a=cnt_{100}+cnt_{101}+cnt_{110}+cnt_{111}$$$
$$$b=cnt_{010}+cnt_{011}+cnt_{110}+cnt_{111}$$$
$$$c=cnt_{001}+cnt_{011}+cnt_{101}+cnt_{111}$$$
$$$a\bigoplus b = cnt_{010}+cnt_{011}+cnt_{100}+cnt_{101}$$$
$$$a\bigoplus c = cnt_{001}+cnt_{011}+cnt_{100}+cnt_{110}$$$
$$$b\bigoplus c = cnt_{001}+cnt_{010}+cnt_{101}+cnt_{110}$$$
$$$a\bigoplus b + a\bigoplus c > b \bigoplus c \iff cnt_{011}+cnt_{100}>0$$$
similar:
$$$cnt_{101}+cnt_{010}>0$$$
$$$cnt_{110}+cnt_{001}>0$$$
then we use digit dp: $$$dp[n][i][j]$$$ means when we consider first $$$n$$$ bits, state of reaching the upper bound is $$$i$$$, state of conditions is $$$j$$$.
Enumerate $$$a_j b_j c_j$$$ for $$$j$$$ from $$$|n|-1$$$ to $$$0$$$ and make transition.
Time complexity is $$$O(2^9 |n|)$$$ where $$$|n|$$$ is the length of input.
The official solution is rather short.
zxyoi's solution
Hint1: Notice that $$$(a\oplus b)\oplus(b\oplus c)=a\oplus c$$$
Hint2: Notice that $$$a\oplus b \leq a + b$$$ since xor ingnores the carrying.
Sol:
We already know two facts above, so let's call $$$dp[i][limit][equal]$$$ refers to the number of legal prefixes that satisfy the constraints, where $$$i$$$ refers to the bits we already considered, $$$limit$$$ has 3 bits, refering to each of $$$a,b,c$$$ has the same prefix with input or not, and $$$equal$$$ has 3 bits, refering to whether the 3 constraints of inequallity is satisfied or not. (That is to say, it's equal or already greater in the prefix , because it can not be less. )
Then we can apply digital-dynamic-programing to calculate each $$$dp[i][limit][equal$$$ in increasing order of $$$i$$$. By enumerating the value of $$$i$$$th charater of $$$a,b,c$$$, we can have a solution in $$$O(n)$$$ time, while the coefficient is 512 (for all transitions between $$$i$$$ and $$$i+1$$$) .