cf1716f sol

我的推式子启蒙题。

暴力做显然超时，考虑换一种方式刻画 $F^k$。

注意到 $F^k$ 等价于给定 $F$ 个不同的数，有 $k$ 个空槽，每次在一个空槽上随便选一个数的方案数。记这 $k$ 个数构成的向量是 $(i_1,i_2,i_3,\cdots,i_k)$。

考虑一组向量 $(j_1,j_2,j_3,\cdots,j_k)$ 满足 $j_i\in\{1,2,3,\cdots,n\}$，那么这组向量对答案的贡献是 $\lceil\frac{m}{2}\rceil^dm^{n-d}$，其中 $d$ 为 $k$ 个数中不同的元素个数。

答案即为 $\sum_{d=1}^k f(d)\binom{n}{d}d!\lceil\frac{m}{2}\rceil^dm^{n-d}$，其中 $f(d)$ 表示 $d$ 个不同的数放到 $k$ 个位置的本质不同方案数，并认为可以通过重排列 $d$ 个数使得两种摆放方式相同的摆放方式为本质相同的，例如在 $d=3,k=4$ 时

注意到 $f(d)$ 是斯特林数定义（$k$ 个不同的球放入 $d$ 个相同袋子中的方案数），于是就做完了。时间复杂度 $O(k^2+Tk)$。