相信大家都还记得曾经因为 EC-Final 名额的事情在群里舌战的同学和主办方。事情的起因就是，参加 ICPC 西安邀请赛的金牌队伍所在学校可以直接获得 EC-Final 名额。
西安邀请赛每年都会在西北工业大学举办，不过比赛和 EC-Final 的不同就在于，队伍实力没有 EC-Final 这么强，而且比赛会在学校的机房进行。
比赛的题目会由西北工业大学自己命题，为了让大家更直观的感受比赛的难度，我们今天来看看 2019 年西安邀请赛的题目（2019 ICPC China Xi'an Invitational Programming Contest）。
因为我们参与了线下赛，所以这里就没有代码分享了。
一点我们现场比赛的记录
- 现场的座位非常挤。
- 热身赛四点求面积这种题目都能锅，提前预感到了正赛锅会比较大。
- 果然正赛连样例都能锅。
- 题面表述乱七八糟，全靠连蒙带猜得知题意。
- 评测队列积压严重。甚至
5 min 才能出结果。
- E 题连 O(nq) 的暴力都能过，出题人造树的数据连个链都没有，怕是用脚造的数据。
- 空调坏了，赛场热的（哔—）
- 上完厕所回来会感觉机房的门相当于一个巨型暖气。
Problem A
贪心。签到。
Problem B
题意：求 prodlimits_{i=1}^{n}prodlimits_{j=1}^{n}prodlimits_{k=1}^{n}m^{gcd(i,j)}[k | gcd(i,j)] 。
随便化一化式子就出来了，不过常数很紧。
题解：用欧拉降幂转化为求和 =sumlimits_{k=1}^{n}kd(k)sumlimits_{i=1}^{n/k}sumlimits_{j=1}^{n/k}[gcd(i,j)==1] 相当于枚举 gcd(i,j)=k 。
注意到 sumlimits_{i=1}^{n}sumlimits_{j=1}^{n}[gcd(i,j)==1]=2sumphi(i)-1 直接用通用莫比乌斯反演会反演显然超时，这样考虑基数就能用杜教筛了。
线性筛预处理前 10^7 的 d(i), phi(i) ，大的 id(i) 可以用交换循环顺序 数论分块求。
Problem C
题意：给定一个圆，圆之外中心高度以下的部分不能被经过，圆内部也不能被经过，求圆上最低点到圆外中心高度之上任意一点的最短路。
题解：先把原点放到圆心，再把终点 x 坐标变成绝对值。
frac {1}{4} pi r 的路径是必走的，然后如果 x>r，从 (r,0) 直线走过去就可以了，如果 $x
Problem D
题意：将军战力有战力点数全部分成两边，有不能再同一边的两两的将军关系，求一种分配使得两边分差最小。
题解：肯定在哪里做到过。二分图染色，然后把小的那一堆两边加上，大的减小的值是一个新的物品，然后就是裸的背包。
Problem E
题意：支持树上某一点到根路径上所有点 and 一个值， or 一个值，链上做 nim 游戏。
题解：显然 nim 游戏就是求个异或。
常规操作，拆位。
and 一个值和 or 一个值，转换一下就是链上所有的数置 0/1 ，线段树维护就好了。
树上的链处理，树链剖分一下。
Problem I
题意：给定数列 a^{k},....,a^{k n-1} (mod p) 和 n 其中 1 le a_i le 10^5 ，求是否有唯一的 a,p le 10^{10} 。
题解：等比数列显然是不唯一的，周期出现但是不包含 1 显然是不存在的。
n le 2显然是不唯一的。剩下的非等比数列一定存在 a[i]^2 not = a[i-1]a[i 1] 然后发现 p | abs(a[i-1]a[i 1]-a[i]^2) 枚举素因数就能求 p 了，然后一个一个验证。
注意会爆 long long ， exBSGS 判 k 是否存在也要改成快速乘。
Problem J
题意：给定一棵有 n 个节点的树，求这棵树上每条路径上，边权异或和为 0 的子路径的数量和。
题解：定义 dep(u) 是 u 的深度（根节点深度为 0），son(u) 是以 u 为根的子树中的节点数，E(u,v) 为 u 到 v 的路径，F(u,v) 是 u 到 v 的路径的边权异或和。
我们可以按 u,v 的位置关系将所有 F(u,v)=0 分类：如果 u 是 v 的祖先，这条路径对答案的贡献是 (n-son(w)) times son(v) ，其中 w 是 v 到 u 路径上除 u 之外深度最深的节点。否则，这条路径对答案的贡献是 son(u) times son(v)。
我们发现，第二种路径可以拆成两条第一种路径，因此维护每个节点向上的第一种路径，并统计在此节点交汇的所有第二种路径的贡献，用启发式合并维护。
Problem L
题意：给定一个长度为 n ，每个元素均不同的序列，可以将偶数位和前面的奇数位互换，可以将前一半和后一半互换（如果有中间元素，中间元素不变），问可以从初始序列达到多少个不同的序列。
题解：找规律。对 n=1,3 的情况特判，剩下的情况里 n %4=0 时答案是 4 ，1 时是 2n，2 时是 n ，3 时是 12。
Problem M
题意：可以给一个飞船升级，每次升级花费 c ，可以通过的路径长度 ;d ，可以通过的边总数 ;e 。求最小的花费，能从 1 到 n 。
题解：二分最小的升级次数。
验证的时候从 1 开始 BFS ，所有能够拓展的边全部拓展，显然 BFS 先到的满足了通过边数最小的要求，可以拓展的边满足了可以通过的路径长度要求。
判断此时 1 到 n 是否联通即可。
