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

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

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
  • Проголосовать: не нравится

»
6 лет назад, # |
← 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)

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

    Can you share your implementation? There are lot's of doubt over it.

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится 
      LL dp[301][2501];
dp[0][1] = 1;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < 2500; j++) {
        dp[i + 1][j * a[i] % (p * q)] += dp[i][j];
    }
}

LL answer = dp[n][0];
      → Ответить
»
6 лет назад, # |
  Проголосовать: нравится 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).

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится -11 Проголосовать: не нравится

    Great explanation, but I believe it may not produce correct output when P == Q.

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится

      You are correct. In that case, redefine B: Bi = 1 if it is divisible by P, and Bi = 2 if it is divisible by P2. We want to find the number of subsets with sum greater than 1. The solution is very similar to the previous one.

      → Ответить
  • »
    »
    6 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится 
    n = 10
p = 8
q = 1
a: 2 2 2 2 2 2 2 2 2 2

    It's seems, like your return 0, which is definitely wrong.

    UPD: Missed that P and Q are primes.

    → Ответить