FastPrepFastPrep
Problem Brief

Sum of Cubes of Beautiful Numbers

NEW GRADOA

You call a number beautiful if it contains at least 1 bit '0' and at most 3 bits '0' in its binary representation. For example, 5 (101) and 8 (1000) are beautiful numbers but numbers like 15 (1111), and 16 (10000) are not. Strings in parentheses are the corresponding binary representations.

You are given Q queries of the type L, R. Consider all beautiful numbers between the range L and R (inclusive). Find the sum of cubes of all such beautiful numbers. Since the sum can be very large, output it modulo 998244353.

Note:

  • Assume 1-based indexing.
  • Do not count leading zeros in binary representation.
  • x modulo y means the remainder when x is divided by y. In particular, if x modulo y = z, then (x-z) is divisible by y and 0 ≤ z < y.

    • Function Description

    Complete the function sumOfCubesOfBeautifulNumbers in the editor.

    sumOfCubesOfBeautifulNumbers has the following parameters:

    1. long[][] queries: a 2D array of queries with each query containing two integers L and R

    Returns

    long integer: the sum of cubes of beautiful numbers in range L and R (inclusive) modulo 998244353

    Input Format

    The first line contains a single integer Q denoting the number of queries. The next Q lines follow. For each line: The first line contains two space-separated integers denoting L and R.

    Output Format

    Print Q space-separated integers, where the integer represents the sum of cubes of beautiful numbers in range L and R (inclusive). Do not forget to take modulo 998244353.

    1Example 1

    Input
    queries = [[5, 8], [10, 15]]
    Output
    [153, 0]
    Explanation

    For the first query, the beautiful numbers between 5 and 8 are 5 (101) and 8 (1000). Their cubes are 125 and 512 respectively. The sum of cubes is 637. Taking modulo 998244353, the result is 637.

    For the second query, there are no beautiful numbers between 10 and 15 as all numbers have either no '0' bits or more than 3 '0' bits in their binary representation. Hence, the sum is 0.

    Constraints

    Limits and guarantees your solution can rely on.

    • 1 <= Q <= 2*10^5
    • 1 <= L <= R <= 10^18
    public long sumOfCubesOfBeautifulNumbers(long[][] queries) {
  // write your code here
}
    Input

    queries

    [[5, 8], [10, 15]]

    Output

    [153, 0]

    Sign in to submit your solution.