注意到 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)。