题解

思路

按所选人数直接写答案是

$$\sum_{x=1}^{N}\binom Nx x^k.$$

用第二类 Stirling 数展开普通幂：

$$x^k=\sum_{j=0}^{k}S(k,j)x^{\underline j}.$$

交换求和后，先指定一个有序的 $j$ 人组，再任意选择其余人员是否加入，可得

$$\sum_x\binom Nx x^{\underline j}=N^{\underline j}2^{N-j}.$$

做法

用递推 $S(t,j)=S(t-1,j-1)+jS(t-1,j)$ 求出第 $k$ 行 Stirling 数。随后依次维护下降幂 $N^{\underline j}$ 和 $2^{N-j}$，累加

$$S(k,j)N^{\underline j}2^{N-j}.$$

因为 $N<10^9+7$，当 $j>N$ 时下降幂为零，只需枚举到 $\min(k,N)$。

子任务 1 可以枚举所有非空子集；子任务 2 可以直接按人数枚举 $x$ 并维护组合数。

复杂度

时间复杂度为 $O(k^2)$，空间复杂度为 $O(k)$。