Great Bitwise Arrays

Hard

0/120

0 upvote

Problem statement

You are given three integers: N, M, and K. Your task is to find the number of "great" arrays of length N.

An array A of length X is considered great if for all i from 2 to X, the condition bitcount(A[i-1] & A[i]) = K holds true. The elements A[i] of the array must satisfy 0 <= A[i] < 2^M.

Since the total number of great arrays can be very large, you must return the count modulo 1,000,000,007.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains an integer N.

The second line contains an integer M.

The third line contains an integer K.

Output Format:

Print a single integer representing the total number of great arrays, modulo 1,000,000,007.

Sample Input 1:

2
2
1

Sample Output 1:

Explanation for Sample 1:

N=2, M=2, K=1. The numbers are in the range [0, 3].
We need to find pairs `(A[0], A[1])` such that `bitcount(A[0] & A[1]) = 1`.
The valid pairs are: `(1,1), (1,3), (2,2), (2,3), (3,1), (3,2)`. Total is 6.

Sample Input 2:

1
5
3

Sample Output 2:

Explanation for Sample 2:

N=1. An array of length 1 has no pairs to check, so any number is valid.
The numbers are in the range `[0, 2^5 - 1]`.
The total count of numbers from 0 to 31 is 32.

Expected Time Complexity:

The expected time complexity is O((2^M)^3 * log N).

Constraints:

1 <= N <= 10^18
1 <= M <= 6
0 <= K <= M

Time limit: 2 sec

Approaches (1)

Approach 1

Dynamic Programming

Time Complexity

Space Complexity

(100% EXP penalty)

Great Bitwise Arrays

Console