Suppose there is an array having at most 10 elements between 1 to 10^18. Suppose the array has elements B1,B2,.Bn. We can choose sequence A1,A2,A3,..An such that 0<=Ai<=Bi. Count How many sequences satisfy A1|A2|A3|..|An=A1+A2+A3+..An, where | is bitwise OR.
3
-
$\begingroup$ Why are the B's considered to form an array rather than a sequence ? This seems immaterial. $\endgroup$– user16034Commented Mar 29, 2023 at 6:58
-
1$\begingroup$ Where is this question coming from ? A real-life problem or a homework ? $\endgroup$– user16034Commented Mar 29, 2023 at 7:00
-
1$\begingroup$ Please credit the original source of this task. Also, posts that consist solely of the statement of an contest- or exercise-style task and a demand for us to solve it are unlikely to be well received here. We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$– D.W. ♦Commented Mar 29, 2023 at 8:37
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Your numbers are less than $10^{18} < 2^{60}$, so only bits 0 to 59 can be set. Prove that for 59 >= b >= 0, bit number b is set in at most one of the $A_i$, and go from there.
