Jeffrey Jiang
Source: Codeforces 1829H
Given an array
Recall that the subsequence of an array
Each test contains multiple test cases. The first line contains the number of test cases
The first line of each test case consists of two integers
The second line of each test case consists of
It is guaranteed that the sum of
For each test case, output a single integer — the number of subsequences that have exactly
For this problem, you are given an array
Here are a couple of notable details of the problem, every member of
Now, the question remains, how do we count the subsequences that results in these numbers?
For this, we can use a dp array that will keep track of the number of subsequences for each number between
This means, for each subsequence count
After updating these counts, we would add
Using these ideas, we can now design an algorithm to solve this problem.
For each testcase
- Get the values for
$n$ and$k$ - Initialize an empty array
$s$ of length 64, whose indicies will correspond to each subsequence count$s_i$ - For each element in
$a$ - Update
$s_{i\&a_j}$ to be$s_{i\&a_j}+s_i$ , for$i = 0$ to$63$ . - Add
$1$ to$s_{a_j}$
- Update
- Return the sum of all
$s_i$ such that$i$ has$k$ set bits.
This algorithm uses:
#include <bits/stdc++.h>
using namespace std;
#define MODVALUE 1000000007
#define ll long long
#define FLP(i,n) for(int i = 0; i < n; ++i)
int main() {
cin.tie(0)->sync_with_stdio(0);
ll answer;
int tests, n;
short val, k;
cin >> tests;
FLP(t,tests){
cin >> n >> k;
answer = 0;
ll valuesSaw[64] = {0};
FLP(i,n){
cin >> val;
FLP(j,64){
valuesSaw[val & j] = (valuesSaw[val & j] + valuesSaw[j])%MODVALUE;
}
valuesSaw[val] = (valuesSaw[val]+1)%MODVALUE;
}
switch(k){
case 0:{
answer = valuesSaw[0];
};break;
case 1:{
short vals[] = {1, 2, 4, 8, 16, 32};
FLP(i,6){
answer = (answer+valuesSaw[vals[i]])%MODVALUE;
}
};break;
case 2:{
short vals[] = {3, 5, 6, 9, 10, 12, 17, 18, 20, 24, 33, 34, 36, 40, 48};
FLP(i,15){
answer = (answer+valuesSaw[vals[i]])%MODVALUE;
}
};break;
case 3:{
short vals[] = {7, 11, 13, 14, 19, 21, 22, 25, 26, 28, 35, 37, 38, 41, 42, 44, 49, 50, 52, 56};
FLP(i,20){
answer = (answer+valuesSaw[vals[i]])%MODVALUE;
}
};break;
case 4:{
short vals[] = {15, 23, 27, 29, 30, 39, 43, 45, 46, 51, 53, 54, 57, 58, 60};
FLP(i,15){
answer = (answer+valuesSaw[vals[i]])%MODVALUE;
}
};break;
case 5:{
short vals[] = {31, 47, 55, 59, 61, 62};
FLP(i,6){
answer = (answer+valuesSaw[vals[i]])%MODVALUE;
}
};break;
case 6:{
answer = valuesSaw[63];
};break;
}
cout << answer << '\n';
}
return 0;
}