XOR Triangle solution codeforces
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≤𝑎,𝑏,𝑐≤𝑛0≤a,b,c≤n such that 𝑎⊕𝑏a⊕b, 𝑏⊕𝑐b⊕c, and 𝑎⊕𝑐a⊕c are the sides of a non-degenerate triangle.
Here, ⊕⊕ denotes the bitwise XOR operation.
You should output the answer modulo 998244353998244353.
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<𝑛<22000000<n<2200000) without leading zeros.
For example, the string 10 is the binary representation of the number 22, while the string 1010 represents the number 1010.
XOR Triangle solution codeforces
Print one integer — the number of triples (𝑎,𝑏,𝑐)(a,b,c) satisfying the conditions described in the statement modulo 998244353998244353.
101
12
1110
780
11011111101010010
141427753
XOR Triangle solution codeforces
In the first test case, 1012=51012=5.
- The triple (𝑎,𝑏,𝑐)=(0,3,5)(a,b,c)=(0,3,5) is valid because (𝑎⊕𝑏,𝑏⊕𝑐,𝑐⊕𝑎)=(3,6,5)(a⊕b,b⊕c,c⊕a)=(3,6,5) are the sides of a non-degenerate triangle.
- The triple (𝑎,𝑏,𝑐)=(1,2,4)(a,b,c)=(1,2,4) is valid because (𝑎⊕𝑏,𝑏⊕𝑐,𝑐⊕𝑎)=(3,6,5)(a⊕b,b⊕c,c⊕a)=(3,6,5) are the sides of a non-degenerate triangle.
The 66 permutations of each of these two triples are all the valid triples, thus the answer is 1212.
In the third test case, 110111111010100102=114514110111111010100102=114514. The full answer (before taking the modulo) is 14664081188081641466408118808164.