ShashwatS1's blog

HELP Count Sub-sequences
By ShashwatS1, history, 3 years ago, In English

You are given the following :-

— An array A of length N
— An integer X

Task

Determine the number of sub-sequences of Array A such that the following condition is satisfied.

— If i1,i2....ik is the indices in the sub-sequence, then ( A[i1] ^ A[i2] ^.....^A[ik] ) & X =0, where ^ represents Bitwise XOR and & represent Bitwise AND operator.

Since, the number of sub-sequences can be large enough, output it modulo 10^9+7.

Example:-

Assumptions

  • N = 4
  • X = 7
  • A[] = [5,2,7,6]

Output:-
2 , one is [5,2,7] another Empty sub-sequence.

Constraints

  • 1<= N <= 1000
  • 1<= X <= 1000
  • 0<= A[i] <= 1000

Sample Input:-
3
1
5 7 1

Sample Output:-
4

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Let's consider a matrix dp[N][1024], where dp[i][j]=the number of ways to get an XOR value of j considering the first i numbers. Then you can transition as folows:

for(j=0;j<1024;++j)
{
    dp[i][j]+=dp[i-1][j];
    dp[i][j^A[i]]+=dp[i-1][j];
}

First assignment caries over the results(Not appending A[i]), second one increases the number of ways to obtain j^A[i] which just means that for all the ways to get j A[i0], A[i1], ..., A[ik] you append to the array the value A[i] getting A[i0], A[i1], ..., A[ik], A[i]. Then after computing the dp, you can simply iterate through dp[N-1][i] and adding it to an answer if (i&X)==0.

Since you only need last column, you can use just 2 vectors to get better memory. Don't forget to do all operations modulo.

Note: The dimensions of the matrix must be 1024 because it is possible to get an XOR value bigger than 1000(i.e. 1, 1000 gives 1001)

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

https://codeforces.com/blog/entry/93666
Already discussed here I guess,just convert transitions to number of ways.

→ Reply