Team Work cf-932E

//Team Work cf-932E
Another alternative solution for E:

Let's give x^k a combinatorial meaning. x^k is the number of combinations of picking k people from the subset with x people with repetition. For each subset we count all combinations and sum those.

Why not switch sums? For each combination we count the number of subsets in which the combination appears, and sum those. This obviously computes the same result.

Assume we have a combination of size k consisting of i distinct people. From which subsets can we construct this combination? Obviously the i people have to be in the subset, but for every other person we have two choices: he is in the subset or he isn't. It doesn't matter. Therefore there are 2^(n - i) such subsets.

Let dp[j][i] be the number of combinations of size j with i distinct people, then the result is . dp[j][i] can be computed very easily with, you guess it, dynamic programming.

To generate a combination with i elements from which j are distinct we have two options.

We can start with a combination with i - 1 elements from which j are distinct, and append an element that already appears in it. => j options to choose the new element => j * dp[i - 1][j].
We can start with a combination with i - 1 elements from which j - 1 are distinct, and append a new element that doesn't appear in the combination => n - (j - 1) possibilities to choose the new element => (n - j + 1) * dp[i - 1][j - 1].