492. Subsets With a Total Divisible by k
Count the NON-EMPTY subsets whose total is divisible by k. Subsets are identified by
position, so equal values at different positions give different subsets.
Print the count modulo 1000000007.
1 2 3, k = 3 -> 3 {3}, {1,2}, {1,2,3}
1 1 1, k = 3 -> 1 only {1,1,1}
## Why the usual table does not apply
Problem 483 indexes the table by the total, which needs the total to be small. Here the
totals reach 2 * 10^14 and the question does not ask about any particular total.
It asks about the total MODULO k, and k is at most 1000. So index the table by the
RESIDUE:
dp[r] = how many subsets so far have total congruent to r mod k
The state is whatever the question can distinguish, and nothing here distinguishes two totals with the same residue. Recognising that is the whole step.
## The recurrence
dp[0] = 1 the empty subset, residue 0
for each value v:
next = copy of dp
for r in 0..k-1:
next[(r + v) mod k] += dp[r]
dp = next
answer = dp[0] - 1
Each value is either left out, which is what the copy preserves, or added, which moves
each residue class to (r + v) mod k.
## Why the copy, and not an in-place loop
Adding v moves a residue FORWARD by v mod k, and residues wrap. So there is no
loop direction that guarantees reading pre-update values, the way a downward loop does
for a plain total. Modular arithmetic has no "downward".
Updating in place lets one value be counted twice on wrap-around, and the count comes out too large.
This is the same reason problem 485 needs a copy per group: whenever the transition is not monotone in the index, the loop direction cannot save you.
## The minus one
dp[0] at the end counts the EMPTY subset too, whose total 0 is divisible by every
k. The question asks for non-empty subsets, so subtract 1.
Under a modulus, subtract carefully: (dp[0] - 1 + MOD) % MOD, because dp[0] can be
0 after reduction.
## Boundaries
1 with k = 2 answers 0. The only non-empty subset has total 1, and 0 is the correct
count rather than -1.
6 3 9 12 with k = 3 answers 15. Every value is divisible by 3, so every one of the
2^4 - 1 non-empty subsets qualifies. That is the maximum and the case that catches an
off-by-one in the minus one.
2 4 6 with k = 2 answers 7, the same situation with three values.
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ k ≤ 1000` - `1 ≤ value ≤ 1000000000`
Input
The first line contains two integers n and k.
The second line contains n space-separated positive integers.
Output
Print the number of non-empty subsets whose total is divisible by k, modulo 1000000007.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.