no_life's blog

Help for a problem
By no_life, history, 6 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?
»
6 years ago, # |
← 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
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it 
      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];
      → Reply
»
6 years ago, # |
  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
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

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

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

      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.

      → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
    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.

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

      P and Q must be primes. Neither 8 nor 1 is prime.

      → Reply