上网翻了一圈题解，只看到了双射然后斯特林数的做法。感觉这个直接容斥的做法比正解的双射更加自然！

为了方便我们接下来的演示，我们此处认为共有 $m$ 个糖果，$n$ 个堆。

我们考虑从小到大依次往某个堆中加入数。

假设共 $a+b$ 个堆，前 $a$ 个堆开头必须为奇数，后 $b$ 个堆开头必须为偶数，但是堆可以为空，这样的方案数为 $f_{a,b}$。

容易发现这样的方案数为

$$f_{a,b}=a^{\lceil\frac m2\rceil}(b+1)^{\lfloor\frac m2\rfloor}$$

因为每次插入一个奇数时恰有 $a$ 个位置可以插入，插入一个偶数时恰有 $b+1$ 个位置可以插入。

可是堆不能为空，因此我们考虑容斥。

设共 $a+b$ 个堆，前 $a$ 个堆开头为奇数，后 $b$ 个堆开头为偶数，堆不可以为空的方案数为 $g_{a,b}$。

我们要求的答案即为

$$\sum_j\binom njg_{j,n-j}$$

而且我们显然有

$$f_{a,b}=\sum_i\sum_j\binom ai\binom bjg_{i,j}$$

设 $F_n=\sum_j\binom njf_{j,n-j}$，$G_n=\sum_j\binom njg_{j,n-j}$，我们只用求出一项 $G_n$。我们有

$$F_n=\sum_j\binom njf_{j,n-j}=\sum_j\binom nj\sum_a\sum_b\binom ja\binom{n-j}bg_{a,b}=\sum_a\sum_b\binom{a+b}{a}g_{a,b}\binom{n}{a+b}2^{n-a-b}=\sum_j2^{n-j}\binom njG_j$$

二项式反演一下，我们得到

$$G_n=\sum_j(-2)^{n-j}\binom{n}{j}F_j$$

因此求出 $F_0\sim F_n$ 即可。

而正如我们开始所说，$f_{a,b}=a^{\lceil\frac m2\rceil}(b+1)^{\lfloor\frac m2\rfloor}$，暴力求和或者一次卷积即可得到 $F_0\sim F_n$。

总复杂度 $O(n^2+n\log m)$，使用 NTT 优化卷积容易做到 $O(n\log m)$。