Count subsequences where AND of elements consists of k set bits | OA | TRICKY | HARD

https://codeforces.com/contest/1829/problem/H

Given an array a, consisting of n positive integers. Count the number of subsequences for which the bitwise AND elements in the subsequence has exactly k single bits in binary representation. The answer can be large, so print it modulo 10^9+7.
Recall that a subsequence of an array a is the sequence that can be obtained from a, removing some (maybe none) of the elements. For example,[1,2,3], [3], [1,3] are subsequences[1,2,3], but[3,2] and [4,5,6] are Not.
note that AND stands for the logical AND operation .

Input data
Each test contains several sets of input data. The first line contains the number of tests t (1≤t≤10^4). This is followed by a description of the input data sets.
The first line of each test case consists of two integers n and k (1≤n≤2⋅10^5 , 0≤k≤6)
The second line of each test case consists of n integers ai(0≤ai≤63)

It is guaranteed that the sum n for all test cases does not exceed 2⋅10^5.

Output
For each test case, print one integer - the number of subsequences whose binary representation has the value of the bitwise AND
has exactly k set bits. The answer can be large, so print it modulo 10^9+7.

Example
input data
6
5 1
1 1 1 1 1
4 0
0 1 2 3
5 1
5 5 7 4 2
1 2
3
12 0
0 2 0 2 0 2 0 2 0 2 0 2
10 6
63 0 63 5 5 63 63 4 12 13
output
31
10
10
1
4032
15

-------------------------------------------------------------------------------------------------------------------------------------

ITERATIVE SOLUTION

#include<bits/stdc++.h>
using namespace std;

void solve(){
    int n;
    int k;
    cin>>n>>k;
    vector<int> arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    long long cnt[64]={0};
    long long tmp[64]={0};
    for(int i=0;i<n;i++){
        memset(tmp,0,sizeof(tmp));
        for(int j=0;j<64;j++){
            (tmp[arr[i] & j]+=cnt[j])%1000000007;
        }
        for(int j=0;j<64;j++){
            cnt[j]+=tmp[j];
            cnt[j]%=1000000007;
        }
        cnt[arr[i]]++;
        cnt[arr[i]]%1000000007;
    }
    long long res=0;
    for(int i=0;i<64;i++){
        if(__builtin_popcount(i)==k){
            res+=cnt[i];
            res%=1000000007;
        }
    }
    cout<<res<<endl;
}

int main(){
    int TC;
    cin>>TC;
    while(TC--){
        solve();
    }
}

---------------------------------------------------------------------------------------------------------------------------------

RECURSIVE SOLUTION

#include<bits/stdc++.h>
using namespace std;

long long MOD=1000000007;

long long dp[200001][64][2];
int N;

// flag here represents whether the AND consists of non empty subsequences

long long helper(vector<int> &arr, int curr, int AND, int k, int flag){
    if(curr==N){
        return __builtin_popcount(AND)==k && flag==1;
    }
    if(dp[curr][AND][flag]!=-1){
        return dp[curr][AND][flag];
    }
    long long IGNORE=helper(arr,curr+1,AND,k,flag);
    long long ACCEPT=0;
    if(flag==1){
        ACCEPT=helper(arr,curr+1,AND & arr[curr],k,flag);
    }
    else{
        ACCEPT=helper(arr,curr+1,arr[curr],k,1);
    }
    return dp[curr][AND][flag]=(ACCEPT+IGNORE)%MOD;
}

void solve(){
    int n;
    int k;
    cin>>n>>k;
    N=n;
    vector<int> arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<64;j++){
            dp[i][j][0]=-1;
            dp[i][j][1]=-1;
        }
    }
    cout<<helper(arr,0,0,k,0)<<endl;
}

int main(){
    int TC;
    cin>>TC;
    while(TC--){
        solve();
    }
}