题解

序列

相当于 a 不能有两个前缀的差是 P 的倍数，也就是前缀模 P 后两两不同，所以答案是 \prod_{i=1}^{n}P-I

时间复杂度：O(n)

彩球

显然答案是 k^n，我们可以用快速幂求 k^n mod P

问题在于如果是用c++写的话，两个 10^18 规模的数乘起来可能用 64 位整数存不下，所以需要写一个类似快速幂的快速乘

时间复杂度：O(\log^2{n})

最优子段

最优的子段显然要么是最大子段和，要么是最小子段和，所以都试一下就好了

时间复杂度：O(n)

公路收费

先枚举会议所在的城市，然后可以算出每条高速公路的收费，选最高的 k 条就好了

时间复杂度：O(n^2\log{n})