CF995F Cowmpany Cowmpensation

题意：给出一棵树，每个点可以填写整数 之一作为权值。

要求满足每个点的权值不大于父亲，问有多少种填写方法。

答案对 取模。，，时限 。

---

做法一：朴素DP + 插值

容易发现总方案数不超过 ，可以猜想答案是关于 的 次多项式。

对 分别求出答案，就能插值得到任意 的答案。

设 为 填写 的方案数。有转移 搞一个前缀和优化就能够 完成 DP，剩下的就是插值。

做法二：转化 + DP

注意到约束只与权值的相对大小有关，可以考虑离散化。

设 为 填写离散化后第 大的数的方案数。

此时不允许跳跃转移：父节点的权值一定等于子节点的 ，或者。

考虑如何转移，仍观察方程 此时可以认为， 计算的就是 “点权值” 的方案数。不难发现，只需把 差分一下，然后邻项相加即可得到 。

设 为最终使用了 种权值的方案数，那么我们可以在 中依次挑选 个数，方案数即为 。

所以 。

做法三：转化 + DP + 容斥

如果你没有设计出新的状态和方程，而是直接使用了旧状态，也可以通过容斥得到答案。

考虑 和 之间的关系。能够发现： 大概意思就是在 个空位中选择 个值填入,中间空着的就是跳掉了。

移项即可递推 这部分复杂度也是 。