|
|
Ok, if you understand how to apply the inclusion-exclusion principle at the toplevel, then you only need to figure out how to calculate in how many ways we can pick bonuses for N workers such that the lowest value is in [A:B] and the highest value is in [C:D].
Suppose calc(N, X, Y) gives the number of ways to pick bonuses in [X:Y] for N people (i.e. (Y-X+1)N if X<=Y, or 0 otherwise) then we can calculate the above as calc(N, A, D) - calc(N, A, C - 1) - calc (N, B + 1, D) + calc(N, B + 1, C - 1).
The way to parse this is that we start with all cases where bonuses are between A and D (regardless of what the minimum or maximum is) and then subtract the cases where the lowest value is higher than B, or the highest value is lower than C, and then we need to add the cases where all values are between B and C back in, because we have subtracted those twice. (I guess that's the inclusion-exclusion principle applied again.) |
