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.

ANSWER

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
 
#define MOD 1000000007
using namespace std;
 
int T,n,K,B;
int f[32][32][2][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]=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[31][0][1][1] = 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[0][B][1][(1<<K)-1] ;
		ans += f[0][B][0][(1<<K)-1] ;
		ans %= MOD ;
		printf( "%d\n",ans );
	}
	
	return 0;
} 
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro