#arc142d. [arc142_d]Deterministic Placing
[arc142_d]Deterministic Placing
给定一棵 个点的树。初始时可以在某些节点上放置一颗棋子,且放置的棋子总数至少为 ,则共有 种放置方案。
定义一次操作为,
- 对于每颗棋子,将其沿着树边移动到与当前节点相邻的一个节点上。
在一次操作内,所有棋子的移动是同时进行的,并且需要遵循以下规则。
-
每条树边最多被一颗棋子经过。
-
移动后每个节点上至多有一颗棋子。
现在你需要统计 种放置方案中,满足以下条件的方案数,对 取模。
- 对于每个非负整数 ,满足以下条件。
- 至少能进行 次操作。
- 无论如何进行这 次操作,最终所有棋子占据的节点集合唯一。
。