Given an array of length n (n<= 5*10^5) and a number k (k<=10^3), We need to count number of pairs in array whose bitwise and is greater than k. Please share your approach, as I am not able to think the effiecient solution.

I was solving this problem Kingdom Division but i don't know where am i going wrong(just the logic), please forgive me if am doing some very stupid mistake here, I have just started to learn DP, below i am presenting my approach :--

my code with explanation

I was struggling to figure out states and transitions for bounded knapsack problem which is the most general case of knapsack problem, so please if someone can share some insights and code for this, it will be very helpful for us.

For those who may not be familiar with this term bounded knapsack:-

The bounded knapsack problem is like the 0/1 knapsack problem, except in this we are also given a count for each item. In other words, each item has a count si associated with it and we can select an item si times(at max) (1 ≤ i ≤ N).

Ok, finally I got this nice article written by Petr !

problem:-

we are given an array of length n(n<=3000) having integers( from -10^6 to 10^6), we need to chose two disjoint (i.e. they should not overlap) sub-arrays of same length from the array so that the product of two sub-arrays is maximum possible , we just need to find here the maximum product that can be attained..

product of two sub-array 'a' and 'b' of length 'k' is defined as follows:- sum of all (a[i]*b[k-i-1])...

for eg:--

arr = {1, 9, 2, 3, 0, 6, 7, 8}

then here maximum product is 104 by picking by sub-arrays of length 3 :- {9, 2, 3} and {6, 7, 8} product = 9*8 + 2*7 + 3*6 = 104, which is maximum possible here...

I think this is a DP problem(maybe i am wrong) but am getting confused in picking states and transition here.. so please help ...