no_life's blog

Help for a problem
By no_life, history, 8 years ago, In English

Given N numbers(A[0], A[1], ...., A[N-1]) and two prime numbers P, Q. Determine the number of subsets whose product is divisible by P*Q.

2<=N<300, P, Q <= 50, A[i] <= 10,000

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

Comments Comments (8)
| Write comment?
»
8 years ago, hide # |
← Rev. 3  
Vote: I like it -9 Vote: I do not like it

Alternative is simple: dp[i][rem]. Where you already consider first i numbers, current remainder by modulo p × q = rem. dp[i][rem] = number of ways to obtaine this configuration. The transitions can be done in p × q, which will produce in final O(npq)

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

We create a new array B, where Bi = 0 if it is not divisible by P or Q, 1 if it is divisible by P, 2 if it is divisible by Q, and 3 if it is divisible by both. We want to find the number of subsets that have bitwise OR equal to 3. Then the answer is equal to:

(number of ways to pick at least one element such that Bi = 1)  ×  (number of ways to pick at least one element such that Bi = 2)  ×  (number of ways to pick any number of elements such that Bi = 0) + (number of ways to pick any number of elements such that Bi = 0)  ×  (number of ways to pick any number of elements such that Bi = 1)  ×  (number of ways to pick any number of elements such that Bi = 2)  ×  (number of ways to pick at least one element such that Bi = 3).

→ Reply