XOR Triangle solution codeforces

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.

Input

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.

Examples
input 

Copy
101
output 

Copy
12
input 

Copy
1110
output 

Copy
780
input 

Copy
11011111101010010
output 

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

Leave a Comment