## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [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 $\left(a,b,c\right)$ with $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 $998\phantom{\rule{thinmathspace}{0ex}}244\phantom{\rule{thinmathspace}{0ex}}353$.

Solution Click Below:-  👉
👇👇👇👇👇

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

The first and only line contains the binary representation of an integer $n$ ($0) 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

Print one integer — the number of triples $\left(a,b,c\right)$ satisfying the conditions described in the statement modulo $998\phantom{\rule{thinmathspace}{0ex}}244\phantom{\rule{thinmathspace}{0ex}}353$.