Round1
C
比特山是一个旅游胜地，它一共有 \(n\) 个景点，按照海拔高度从低到高依次编号为 \(1\) 到 \(n\)。为了更好地帮助游客们欣赏这里的风景，人们在上面搭建了 \(m\) 条缆车路线。每条缆车路线只可能把游客们从某个海拔较低的景点运送到另一个海拔较高的景点。 在每个景点都有一家纪念品连锁商店，其中第 \(i\) 个景点的商店隶属第 \(c_i\) 号公司，两家连锁店 \((i,j)\) 隶属同一公司当且仅当 \(c_i=c_j\)。每家公司都有新客优惠活动，其中第\(i\)家公司对于新客的优惠红包为 \(w_i\) 元，一旦领取了隶属该公司的某家连锁店的一份红包，就不能再领取该公司所有分店的红包。 你正在 \(1\) 号景点，你将会搭乘缆车去往各个景点，每到一个景点，你都可以领取该景点的连锁商店的新客优惠红包（包括 \(1\) 号景点）。当然，同一家公司的红包最多只能领一次。请写一个程序，对于每个可能的终点 \(k\)，找到一条从 \(1\) 号景点出发到达 \(k\) 号景点的游览路线，使得可以领取到总金额最多的优惠红包。
\(2\leq n\leq 36\), \(1\leq m\leq \frac{n(n-1)}{2}\)
我们发现，出现次数 \(=1\) 的店铺我们可以直接累加贡献，然后我们只用状压出现次数 \(>1\) 的数，时间复杂度 \(O(2^{\frac n 2}n^2)\) 。
E
在比特超市有 \(n\) 种商品，依次编号为 \(1\) 到 \(n\)，购买一件第 \(i\) 种商品的价格为 \(i\) 元，其价值为 \(v_i\)。由于备货充足，每种商品都可以购买任意非负整数件。 小Q计划购买恰好 \(k\) (\(1\leq k\leq 10^9\)) 件商品，并计算出了 \(f_0,f_1,f_2,\dots,f_{n-1}\)，其中 \(f_i\) 表示购买 \(k\) 件商品且商品价格之和对 \(n\) 取模的余数恰好为 \(i\) 的所有方案中商品价值之和的最大可能值。 一天过去之后，健忘的小Q忘记了昨天做的购物计划中到底要买多少件物品，请写一个程序根据小Q的回忆找到 \(k\) 的值。
\(1\leq n\leq 1\,000,1\leq |v_i|\leq 10^9 ,-10^{18}\leq f_i\leq 10^{18}\)
首先，如果 \(k\) 存在，那么 \(k\) 一定是 \(\frac {\max f}{\max v}\)，然后问题在于判断 \(k\) 是不是答案。
对于这个，我们用类似于快速幂的方式对 \(v\) 进行循环卷积，一次是 \(O(n^2)\) 的，总时间复杂度 \(O(n^2\log k)\)。
Round 2
B
给定一颗树，点有点权，动态加入关键点或者删除，维护所有关键点的极小联通子树的点权和。
vp 时被诈骗了，点权转边权，然后加上所有点 lca 的点权就行了。
K
给定一个数列 [\(a_1\),\(a_2\),…,\(a_n\)] ，这个数列中只包含 0 和正整数，保证所有 \(a_i\) 的和不超过 \(10^6\)。
定义一个区间 \([l,r]\) 的权值为区间内所有元素的和。
依据这个权值对所有 \(n(n+1)/2\) 个区间按照权值从小到大的顺序排序。
接下来给你 \(m\) 个询问，每个询问给出一个 \(k\) ，请你输出排第 \(k\) 的区间的权值
\(1\le n,m\le 10^6,1\le k\le \frac {(n+1)n} 2\)
第一眼，什么 sb 超级钢琴。
第二眼：\(k\) 辣么大，没事了。
由于 \(a_i\) 总和是 \(O(n)\) 级别，我们可以在值域上找思路。
考虑现在又两个前缀和 \(S_l\) 和 \(S_r\) ，那么我们会使 \(S_r-S_{l-1}\) 答案增加 \(1\)，发现是 \(S_r\) 和 \(-S_{l-1}\) 的和，所以我们可以用 FFT 来快速卷积，对于 \(-S_{l-1}\) 的部分，我们令其加上 \(10^6\) 就可以了。