XOR Triangle solution codeforces – You are given a positive integer šn. SinceĀ šnĀ may be very large, you are given its binary representation.
Table of Contents
[Solution] XOR Triangle solution codeforces
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.
[Solution] 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
[Solution] 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.