# How to choose a subset?

QUESTION

Given a set S of first N non-negative integers i.e. S = {0, 1, 2, …, N}.\n\nFind number of ways of choosing a K size subset of S with the property that the XOR-sum of all chosen integers has exactly B set bits in its binary representation (i.e. the bits that are equal to 1). \n\nSince the answer can be large, output it modulo (10^9 + 7). Please refer to notes section for formal definition of XOR-sum.\n\nInput\nThe first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.\n\nThe only line of each test case contains three space-separated integers N, K and B.\n\nOutput\nFor each test case, output a single line containing the answer to the corresponding test case.\n.

``````#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>

#define MOD 1000000007
using namespace std;

int T,n,K,B;
int f[1<<7] , num[1<<7] , c[1<<7][1<<7] ;
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
cin>>T;
while(T--){
scanf("%d%d%d",&n,&K,&B);

num=0;
for ( int l=1;l<(1<<K);l++ )
num[l] = num[l>>1]^(l&1) ;

memset( c,-1,sizeof(c) );
for ( int k=0 ; k<(1<<K) ; k++ )
for ( int l=0 ; l<(1<<K) ; l++ ) {
if ( !(k&1) ) continue ;

int t1 = 1 , t2 , ok = 1 , nk = k ;
for ( t2=2 ; t2<=K+1 ; t2++ )
if ( t2==K+1 || ( k&(1<<t2-1) ) ) {
int app = 0 ;
for ( int p = t1 ; p < t2 ; p++ ) {
if ( l&(1<<p-1) )
if ( app == 1 ) ok = 0 ; else;
else {
if (!app) nk |= (1<<p-1) ;
app = 1 ;
}
}
t1 = t2 ;
}
if ( !ok ) continue ;
c[k][l] = nk ;
}

memset( f,0,sizeof(f) );
f = 1 ;
for ( int i=31;i>=1;i-- )
for ( int j=0;j<=B;j++ )
for ( int o=0;o<=1;o++ )
for ( int k=0;k<(1<<K);k++ ) {
if ( !f[i][j][o][k] ) continue ;

for ( int l=0;l<(1<<K);l++ ) {
if ( c[k][l]==-1 ) continue;
if ( o && (l&1) && !( (1<<i-1)&n ) ) continue ;

int nk = c[k][l] ;
int no ;
if ( !o ) no = 0 ;
else {
if ( l&1 ) no = 1 ; else
if ( !((1<<i-1)&n) ) no = 1 ; else
no = 0 ;
}

f[i-1][j+num[l]][no][nk] += f[i][j][o][k] ;
f[i-1][j+num[l]][no][nk] %= MOD ;
}
}
int ans = 0 ;
ans += f[B][(1<<K)-1] ;
ans += f[B][(1<<K)-1] ;
ans %= MOD ;
printf( "%d\n",ans );
}

return 0;
} ``````  