HDU Multi-University Training 2019, Contest 3

Segment tree for optimizing DP: Problem B
First we can binary search on the answer, and then we consider a $O(n^2)$ DP where $dp[i]$ means the maximum number of partitions we can have ending at $i$th position. Then transition is as follows $$dp[i] = max_{j} (dp[j]) \text{ s.t. } sum[i] – sum[j] \leq val$$. Since the constraints is in a continuous range of prefix sum, we can keep them in a segment tree to do fast maximum queries.

Wilson’s Theorem: Problem F
For any prime $p$, we have $$(p – 1)! = -1 \text{ (mod } p)$$

Leave a Reply

Your email address will not be published. Required fields are marked *