P10053 [CCO2022] Bi-ing Lottery Treekets 讲解

zrl123456 · 2024-08-22 12:58:19 · 题解

P10053 [CCO2022] Bi-ing Lottery Treekets

题目考察：数论，组合数学，递推，树形 dp。
题目简述：
给定一棵有 n 个结点的树，有 k 个球，第 i 个球将被投放在树上的 x_i 号点上，但球的投放的顺序未确定，对于每次球被投放，他都会：

1. 球刚被投放：
   • 若其左右儿子均没有球，则可以向任意方向往下滚。
   • 若左儿子或右儿子上有球，则向另一方向往下滚。
   • 若左儿子和右儿子上都有球，则结束行动。
   • 若该位置有球，则该方案不合法。
2. 球是滚下来的：
   • 若其左右儿子均没有球，则向原来的方向往下滚。
   • 若左儿子或右儿子上有球，则向另一方向往下滚。
   • 若左儿子和右儿子上都有球，则结束行动。

定义 ans_i 是最终落在 i 号点上的球，没有则为 0，问最后的合法的 ans 的个数对 10^9+7 取模的结果。
数据范围：

• 1\le n,k\le 4000
• \forall i\in[1,n],1\le a_i\le n

  考虑树形 dp。

设 f_{i,j} 为在 i 号点上有 j 个球落入了这里的合法方案数（这里的“落入”不含投放的球），那么我们枚举 l 代表在投放在 i 点的球中有 l 个按照原来的方向往下落，这个转移方程需要含以下几部分：

• 设在 i 点上投放了 a_i 个球，则我们需要在其中选出 l 个球，即 \displaystyle\binom{a_i}{l}。
• 设 son_{i,0/1} 为 i 点的左/右儿子，vis=0/1 为他原本的方向：左/右，b_i 代表在 i 的子树内有多少点空着。则我们需要拿到 vis 方向儿子上的方案数，则为：f_{son_{u,vis},\min(j+l,b_{son_{u,vis}})}，因为最多有 \min(j+l,b_{son_{u,vis}}) 个球按原来的方向往下落。
• 我们还需要在往这边落的 l 个球中排顺序，由于它是带顺序的，所以答案是 l^{\underline{\min(j+l,b_{son_{u,vis}})}}。
• 我们统计右儿子的方案数的方法同上，但要注意可能有一个球停在 i 点，故答案为 f_{son_{u,[vis=0]},a_i+j-\min(j+k,b_{son_{u,vis}})-[j==b_i]}。
• 同上，我们也要排顺序，答案是 (a_i-l)^{\underline{a_i+j-\min(j+k,b_{son_{u,vis}})}}。

那么我们将上面的所有数相乘累加即可。

代码