AIex_2oo8's blog

Question from Insomnia Final
By AIex_2oo8, history, 6 years ago, In English

Question You are given an array A of n integers. Let the maximum possible bitwise OR of any subsequence of elements of the array be M. You need to print n integers numbered from 1 to n. The ith integer denotes the number of distinct subsequences of size i of the array whose bitwise OR is equal to M. Since the integers can be very large, print each of them modulo 10^9+ 7.

Note: Two subsequences are distinct if there exists at least one postion of the array which is included in one of the subsequences and not so in the other.

CONSTRAINTS

1 ≤ n ≤ 5000

0 ≤ Ai < 2^12

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

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

Can you provide the link of insomnia final?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://www.hackerearth.com/challenge/college/insomnia-onsite-final-round-2018/

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Bruteforce + Inclusion-exclusion Principle + Binomial Coefficients.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Inclusion Exclusion on what ?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      On the bitwise-OR value.

      For each i, we need to calculate "how many subsequences of length i whose bitwise-OR result is a subset of v" for each v.

      → Reply