AGC054B Greedy Division 发表于 2025-02-22 更新于 2025-02-26 分类于 算法竞赛 ， 题 ， AtCoder 阅读次数： 题意：给出序列 。用一个排列 将序列 打乱。 接下来，有两个变量 ，初始时为 。 逐个考虑 ，若 ，则 加上 ，否则 加上 。 求有多少个排列 ，使得最终 。答案对 取模。 。 将 分成两个和相同的集合 。钦定 。 将这两个集合内部的顺序任意打乱，然后考虑它们归并的方案数。 不难发现，由于贪心的决策是确定的，归并的方案数是唯一的。 于是，方案数为 。 接下来用 DP 求出划分集合的方案数。记 表示选了 个数和为 的方案数。 记 ，则答案为： 复杂度为 。