题目大意

对于一个长 nn 的画布，每个位置可以被染成 1∼m1 \sim m 的颜色中的一种。若恰好出现了 ss 次的颜色有 kk 种，则获得了 wkw_k 的愉悦度。求所有涂法的愉悦度的和。

分析

考虑钦定 ii 种颜色被染了 ss 次，剩下不做限定，则方案数为

fi=(mi)n!(s!)i(n−si)!(n−si)m−i f_i = \binom{m}{i} \frac{n!}{(s!)^i (n - si)!} (n - si)^{m - i}

那么恰好 kk 个集合是其交集可以通过二项式反演求得

ak=∑i=km(−1)i−k(ik)fi a_k = \sum_{i=k}^m (-1)^{i-k} \binom{i}{k} f_i

这个式子可以推卷积，有空补上过程。

全部代码请看：Luogu/4x/P4491.cpp。

参考