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

Help for a problem
Автор no_life, история, 8 лет назад, По-английски

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

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

»
8 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится -9 Проголосовать: не нравится

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)

→ Ответить
»
8 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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).

→ Ответить