[Solution] XOR Triangle Codeforces Solution 2022

E. XOR Triangle

time limit per test

4 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

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\le a,b,c\le 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 998244353$998244353$.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

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

Perfect Permutation Codeforces Solution

Party Codeforces Solution

Color the Picture Codeforces Solution

Rain Codeforces Solution

XOR Triangle Codeforces Solution

The first and only line contains the binary representation of an integer 𝑛$n$ (0<𝑛<2200000$0<n<2^{200000}$) without leading zeros.

For example, the string 10 is the binary representation of the number 2$2$, while the string 1010 represents the number 10$10$.

Output

Print one integer — the number of triples (𝑎,𝑏,𝑐)$(a,b,c)$ satisfying the conditions described in the statement modulo 998244353$998244353$.