sfiction/selection/CodeChef

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
- TULIPS, [树, 分块], 总共只涉及2n个集合，且相互之间存在树形关系。重新排列结点，使得所有集合变为独立区间。分块，每块维护对应的有序序列。O(n^1.5)。
- TUPLES, [数论, 容斥, FFT], 注意到359999=599*601，首先将Xi用其对509和601某个原根的指标表示，然后用拉链法做二维FFT，统计所有Yij。其中有一些不存在相应指标的数（599或601的倍数）需要特殊处理。最后用容斥计数。O(ModlogMod)。
- OAK, [数据结构], 查询离线，因此可以求出版本树，对版本树轻重链剖分，先处理轻儿子，这样只需为每条链维护一个可持久化版本，链上的移动无需可持久化。空间复杂度仅为O(nlogV)。V为版本数。本题的查询需要同时处理链和子树情形，需要特殊排列的轻重链剖分，使得DFS序在子树意义上连续，链则最多分为logn段。
- POWSUMS, [代数], 利用n元基本对称多项式和n元k次幂和之间的相互表示，先计算基本对称多项式的值，然后得到>n的k次幂和的递推式。本题矩阵乘法不够快，因为是线性递推，可以使用Cayley-Hamilton Theorem优化，单步包括多项式相乘和高次项化为低次项，前者可以用fft优化为nlogn，后者为nk，其中k为递推式中非零项数，因此复杂度为O(n(logn+k)logm)，本题递推式较为稠密，只能做到O(n^2logm)。
- WESTAND, [贪心], K很小，首先枚举所选chef。一个显然的贪心是，在总工作量一定的情况下，order越多越好，这样能让更多chef参与工作。考虑按截止时间从后往前处理，将仍需处理的order按dish从大到小排序。根据之前所述的贪心，应该让各order尽可能平均，显然dish更大的order应该分配速度更快的chef，对于相同dish应该让他们的chef交替工作，即取均值。计算当前分配方式下，最近的order顺序发生变化的时刻。O(2^nm^2)。
}}}

- TULIPS, [树, 分块], 总共只涉及2n个集合，且相互之间存在树形关系。重新排列结点，使得所有集合变为独立区间。分块，每块维护对应的有序序列。O(n^1.5)。
- TUPLES, [数论, 容斥, FFT], 注意到359999=599*601，首先将Xi用其对509和601某个原根的指标表示，然后用拉链法做二维FFT，统计所有Yij。其中有一些不存在相应指标的数（599或601的倍数）需要特殊处理。最后用容斥计数。O(ModlogMod)。
- OAK, [数据结构], 查询离线，因此可以求出版本树，对版本树轻重链剖分，先处理轻儿子，这样只需为每条链维护一个可持久化版本，链上的移动无需可持久化。空间复杂度仅为O(nlogV)。V为版本数。本题的查询需要同时处理链和子树情形，需要特殊排列的轻重链剖分，使得DFS序在子树意义上连续，链则最多分为logn段。
- POWSUMS, [代数], 利用n元基本对称多项式和n元k次幂和之间的相互表示，先计算基本对称多项式的值，然后得到>n的k次幂和的递推式。本题矩阵乘法不够快，因为是线性递推，可以使用Cayley-Hamilton Theorem优化，单步包括多项式相乘和高次项化为低次项，前者可以用fft优化为nlogn，后者为nk，其中k为递推式中非零项数，因此复杂度为O(n(logn+k)logm)，本题递推式较为稠密，只能做到O(n^2logm)。
- WESTAND, [贪心], K很小，首先枚举所选chef。一个显然的贪心是，在总工作量一定的情况下，order越多越好，这样能让更多chef参与工作。考虑按截止时间从后往前处理，将仍需处理的order按dish从大到小排序。根据之前所述的贪心，应该让各order尽可能平均，显然dish更大的order应该分配速度更快的chef，对于相同dish应该让他们的chef交替工作，即取均值。计算当前分配方式下，最近的order顺序发生变化的时刻。O(2^nm^2)。