Блог пользователя ShashwatS1

HELP Count Sub-sequences
Автор ShashwatS1, история, 3 года назад, По-английски

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

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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)

→ Ответить
»
3 года назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить