2018 CCPC Online Contest

oxx

比赛链接[problemset]

一场趣味十足，大部分时间看不到榜，没有feedback的OI比赛

Problem A

Solved by dreamcloud(-2).

题意：有n天，告诉你某个货物每一天的价格，一开始你没有货物，你可以选择在第i天买进一次该货物，或者卖出一次该货物。问你最高能收获多少钱，最少的交易次数

题解：贪心，从后往前扫，维护一个买了的货物价格的优先队列和还没进行交易价格的优先队列，这时，如果新来一个货物，如果要买的话，有两种情况：其一，之前某一次买的价格比我现在买的价格要高，则将之前买的货物价格替换成当前价格，并将其归为没进行教育的队列中，交易次数不变；其二，没进行交易价格的优先队列中最大值比我当前价格要高，则买进我当前的价格，选择最大值卖出，交易次数加二。两种情况择优进行。如果两种情况都不满足，则选择将其归为未操作队列中。

Problem B

Upsolved by dreamcloud.

题意：考虑等式 $a_i x_i \equiv 1 \pmod m$。有些 $a_i = -1$。求把 $-1$ 的地方填成 $[0,m)$ 之间的正整数，使得 $x_i$ 有解的方案数。然后对 $1 \le m \le n$ 求和。

题解：记 $-1$ 位置的数量为 $cnt$，剩下的 $a_i$ 的 gcd 为 $X$。

首先我们讨论 $X>0$ 的情况（即 $a_i$ 不全是 $0$ 和 $-1$）。 $g(m) = \sum_{d|(X,m)} \mu(d) (\frac{m}{d})^{cnt}$

[math]\displaystyle{ \begin{align}ans &= \sum_{m=1}^n \sum_{d | (X, m)} \mu(d) (\frac{m}{d})^{cnt} \\ &= \sum_{d|X}\mu(d) \sum_{d|m}^n (\frac{m}{d})^{cnt}\\ &= \sum_{d|X}\mu(d) \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} i^{cnt}\\ \end{align} }[/math]

后面是等幂求和。利用伯努利数可解。前面是可以利用容炽原理

对于 $X=0$ 的情况，所求式就变成 $\sum_{m=1}^n \sum_{d | m} \mu(d) (\frac{m}{d})^x$。令 $g(m) = \sum_{d|m} \mu(d) (\frac{m}{d})^{cnt}$。注意到 $g(m)$ 是两个积性函数的狄利克雷卷积，也具有积性。同时，反向运用反演公式可以得到原函数 $f(n) = n^{cnt} = \sum_{d|n} g(d)$。所以，$g(n) = n^{cnt} - \sum_{d|n,d<n} g(d)$。因为n很大，考虑使用杜教筛（推导）。

[math]\displaystyle{ \begin{align} S(n) &= \sum_{i=1}^n g(i) \\ &= \sum_{i=1}^n \left(i^{cnt} - \sum_{d|i, d\lt i} g(d) \right) \\ &= \sum_{i=1}^n i^{cnt} - \sum_{i=1}^n \sum_{d|i,d\lt i} g(d) \\ &= \sum_{i=1}^n i^{cnt} - \sum_{d=2}^n \sum_{d | i}^{n} g(\frac{i}{d}) \\ &= \sum_{i=1}^n i^{cnt} - \sum_{d=2}^n S(\lfloor \frac{n}{d} \rfloor) \end{align} }[/math]

因为每组的$cnt$都不一样，但是k很小，只有50，所以预处理每个k。

Problem C

Solved by oxx1108.

题意：在环中重载加法和乘法，使得在满足$(m + n) ^ p = m ^ p + n ^ p$ $p$是素数

题解：直接重载取模意义下的加和乘就行了。证明费马小定理。

Problem D

Solved by oxx1108.

题意：给定$a$和$n$求$b$和$c$，求满足$a ^ n + b ^ n = c ^ n$ 一组$b$,$c$

题解：n一定等于1或者2，然后1的时候显然，2的时候勾股数构造一下就可以了。（$a$为2时平方无解，但是出题人友好地去掉了这个情况）

Problem E

Solved by oxx1108.

题意：求$(A+\sqrt{B})^n$二项式定理展开的奇数项的和（含根号项）$mod$ $p$

题解：答案为$((A+\sqrt{B})^n - (A+\sqrt{B})^n) / 2$，实现一下带根号的乘法然后快速幂即可。 注意不能直接求2的逆元，因为题目没有保证时素数，所以对$p * 2$取模最后再对答案除2即可。

Problem F

Unsolved.

题意：

题解：

Problem G

Upsolved by Xiejiadong(-5).

场上代码写的又臭又长，调都调不动，一对拍，问题还特别多。

题意：任意选择一个位置开始跳$m$次，每次跳的下一个都是$(i+k)%n$使得获得的价值最大。

题解：显然，所有的跳跃都是好几个循环节，先把所有的循环节抠出来，然后就是在循环节上面做最大连续子序列和，但是不能暴力的做，暴力做的复杂度是$O(n^2)$，我们用类似滑动窗口的技巧，$O(n)$的处理一下所有位置开始咋最大连续子序列和就可以了。

Problem H

Unsolved.

题意：

题解：

Problem I

Solved by oxx1108 & dreamcloud & Xiejiadong.

题意：按照一个排列的顺序依次按照最短路径访问相邻的节点会得到整个路径的和，求按照所有的全排列来遍历树的路径长度总和。

题解：用dfs求出两两点对之间的最短距离总和，模板题。其次就是所有边的总和对最终答案的贡献值，贡献是$(n-2)!*(n-1)*2$

Problem J

Solved by dreamcloud.

题意：从$(0,0)$出发到$(10^9,10^9)$,每次只能向右、向下或者右下，有若干格点，格点上有积分，只有从$(x−1,y−1)$走到该位置才能得到积分，求最高积分。

题解：先按照x坐标排序，然后可以写出dp式子，为$dp[j] = max（dp[i] + val[j]）(i \lt j \&\& x[i] \lt x[j] \&\& y[i] \lt y[j])$，由于x坐标已经是从大大小排序，只需要维护对应y坐标时的最大值，利用线段树维护最大值可以实现。

ECNU Foreigners

Problem A

Solved by kblack. 00:49 (+)

题意：有 $n$ 次机会以 $a_i$ 的价格买入或卖出同一类物品，求最大获益。

题解：考虑贪心，定义一个 $pair(x, y)$ 表示 当前可以以 $x$ 的价格获得一种物品，$y$ 指示这种物品是之前卖出的还是要全新买的（影响交易次数），相当于引入了一个后悔机制，每次取可以交易的最便宜的物品，更新后重新扔进堆里就好了。

Problem B

Upsolved by ultmaster & zerol.

题意：考虑等式 $a_i x_i \equiv 1 \pmod m$。有些 $a_i = -1$。求把 $-1$ 的地方填成 $[0,m)$ 之间的正整数，使得 $x_i$ 有解的方案数。然后对 $1 \le m \le n$ 求和。

题解：记 $-1$ 位置的数量为 $x$，剩下的 $a_i$ 的 gcd 为 $A$。特别的，$\gcd (z, 0) = z$ 对所有正整数成立。（所以 $A$ 算之前记为 $0$，然后每次碰到一个大于 $0$ 的数 $t$，令 $A = \gcd(A, t)$。）然后，所求式即为 $\sum_{m=1}^n \sum_{d | (A, m)} \mu(d) (\frac{m}{d})^x$。（考虑容斥，这一步跟 牛客最后一场多校 的 E 非常类似。）

首先我们讨论 $A>0$ 的情况（即 $a_i$ 不全是 $0$ 和 $-1$）。

[math]\displaystyle{ \begin{align}ans &= \sum_{m=1}^n \sum_{d | (A, m)} \mu(d) (\frac{m}{d})^x \\ &\overset{(A,m) = D}{=} \sum_{D|A} \sum_{m=1}^n [(A,m) = D] \sum_{d|D} \mu(d) (\frac{m}{d})^x \\ &\overset{m = Dg}{=} \sum_{D|A} \sum_{g=1}^{\lfloor n/D \rfloor} [(\frac{A}{D}, g) = 1] \sum_{d|D} \mu(d) (\frac{Dg}{d})^x \\ &= \sum_{D|A} \left( \sum_{d|D} \mu(d) (\frac{D}{d})^x \right) \left( \sum_{g=1}^{\lfloor n/D \rfloor} [(\frac{A}{D}, g) = 1] g^x \right) \\ &\overset{g = it}{=} \sum_{D|A} \left( \sum_{d|D} \mu(d) (\frac{D}{d})^x \right) \left( \sum_{t|(A/D) } \mu(t) \sum_{i=1}^{\lfloor n/D/t \rfloor} (it)^x \right) \\ &= \sum_{D|A} \left( \sum_{d|D} \mu(d) (\frac{D}{d})^x \right) \left( \sum_{t|(A/D) } \mu(t) t^x \sum_{i=1}^{\lfloor n/D/t \rfloor} i^x \right)\end{align} }[/math]

考虑如何计算答案。首先式中的 $D,d,t$ 全都是 $A$ 的因数，可以预处理 $A$ 的所有因子（因子个数是根号级别的，顶多在 3k 左右），以及这些因子的 $\mu$。然后在这些因子中间暴力枚举暴力算。注意不要预处理太多的东西 (因为 64 MB 的内存毕竟有些小)。最后一部分要算 $\sum_{i=1}^{\lfloor n/D/t \rfloor} i^x$，这是一个等幂求和。利用伯努利数可解。

对于 $A=0$ 的情况，所求式就变成 $\sum_{m=1}^n \sum_{d | m} \mu(d) (\frac{m}{d})^x$。令 $g(n) = \sum_{d|n} \mu(d) (\frac{m}{d})^x$。注意到 $g(n)$ 是两个积性函数的狄利克雷卷积，也具有积性。同时，反向运用反演公式可以得到原函数 $f(n) = n^x = \sum_{d|n} g(d)$。所以，$g(n) = n^x - \sum_{d|n,d<n} g(d)$。考虑使用杜教筛（推导）。

[math]\displaystyle{ \begin{align}S(n) &= \sum_{i=1}^n g(i) \\ &= \sum_{i=1}^n \left(i^x - \sum_{d|i, d\lt i} g(d) \right) \\ &= \sum_{i=1}^n i^x - \sum_{i=1}^n \sum_{d|i,d\lt i} g(d) \\ &= \sum_{i=1}^n i^x - \sum_{i/d=2}^n \sum_{d=1}^{\lfloor n/(i/d) \rfloor} g(d) \\ &= \sum_{i=1}^n i^x - \sum_{i/d=2}^n S(\lfloor \frac{n}{i/d} \rfloor) \\ &= \sum_{i=1}^n i^x - \sum_{i=2}^n S(\lfloor \frac{n}{i} \rfloor) \end{align} }[/math]

因为每组 case 的 $x$ 不同，所以每次都要对 $n^{2/3}$ 之内的 $g(n)$ 和 $S(n)$ 使用线性筛进行预处理，然后运行杜教筛即可。注意到这个地方又存在一个等幂求和，不预处理的话，复杂度表面上看起来是 $10^6 \times 50$，但实际上也足以通过本题。

zerol:

[math]\displaystyle{ \begin{eqnarray} && \sum_{m=1}^M \sum_{d|(A,m)} \mu(d) (\frac{m}{d})^C \\ &=& \sum_{m=1}^M m^C \sum_{d|(A,m)} \mu(d) d^{-C} \\ &=& \sum_{d|A}\mu(d) d^{-C} \sum_{d|m }^{M} m^C \\ &=& \sum_{d|A}\mu(d) d^{-C} \sum_{k=1}^{\lfloor \frac{M}{d} \rfloor} (kd)^C \\ &=& \sum_{d|A}\mu(d) \sum_{k=1}^{\lfloor \frac{M}{d} \rfloor} k^C \end{eqnarray} }[/math]

$A=0$ 时就是求 $S(M)=\sum_{m=1}^M \sum_{d|A} \mu(d) (\frac{m}{d})^C $，设 $g(n)=n^C$，那么求和式转化为 $\sum_{m=1}^M (f=\mu*g)(m)$。

根据反演公式（$f*1=g$，按照杜教筛，配的积性函数就是 $1$），有 [math]\displaystyle{ g(n)=\sum_{d|n}f(d) \\ f(n)=g(n)-\sum_{d|n,d\ne n}f(d) \\ \begin{eqnarray} S(n)&=&\sum_{i=1}^n g(i)-\sum_{i= 1}^{n}\sum_{d|i,d\lt i}f(d) \\ &\overset{t=\frac{i}{d}}{=}& \sum_{i=1}^n g(i)-\sum_{t=2}^{n} S(\lfloor \frac{n}{t} \rfloor) \end{eqnarray} }[/math]

由于函数 $g$ 和函数 $1$ 能够方便求出前缀和，那么杜教筛就成立了，前 $n^{2/3}$ 项 $S(n)$ 还是需要预处理的。

Problem C

Solved by zerol. 00:50 (+)

题意：在 $\{0,1,2,\cdots,p-1\}$ 中定义加法和乘法，满足$(m + n) ^ p = m ^ p + n ^ p$，其中 $p$ 是素数。而且至少存在一个数 $q$ 满足 $\{q^k | k \in \{0,1,2,\cdots,p-1\} \}=\{0,1,2,\cdots,p-1\}$

题解：定义为 $\mathbb{Z}_p$ 即可，后面那个条件是原根的定义（对于素数一定存在）。

Problem D

Solved by zerol. 00:29 (+)

题意：给定 $a$ 和 $n$，求一组 $b$和$c$，满足$a ^ n + b ^ n = c ^ n$。

题解：对于 $n\ge 3$，由费马大定理得知无解。$n \in \{0,1\}$ 随便构造。$n=2$ 时找因数用勾股数的一般形式构造的。

zerol：方便的做法是把 $a$ 中 2 的幂提取出来。然后 $a^2 + ((a+1)(a-1)/2)^2= (((a+1)^2+(a-1)^2)/4)^2$。

Problem E

Solved by ultmaster. 02:50 (+1)

题意：求 $\displaystyle \sum_{i=1}^n [i \equiv 1 \pmod 2] \frac{a^{n-i} \sqrt{b}^i n!}{i! (n-i)!}$。

题解：简单观察，或者使用 Mathematica 化简之后就可以得到所求式是 $\displaystyle \frac{1}{2} \left( (a + \sqrt{b})^n - (a - \sqrt{b})^n \right)$。发现 $(a+\sqrt{b})^n$ 一定具有 $a + c \sqrt{b}$ 的形式，直接快速幂即可。最后要把 $\sqrt{b}$ 中的平方因子提出来，暴力搞好像会 TLE（可能是前面模多了），要预处理。

处理模数要用到经典的技巧：先模 $2p$，然后最后除以 2。

Problem F

Unsolved. (-1)

Problem G

Solved by zerol. 03:03 (+3)

题意：给一个环，从任意点出发，每次跳 k 步，问最多 m 步内走过的格子上的数值之和的最大值。

题解：对于 gcd(n,k) 个环，分别考虑每一个，就是长度不超过 k 的最大子段和。（这题好像去年多校有。）然后设 m = len * q + r，根据和的正负，先走完 $\max(q-1,0)$ 圈，剩下的把环复制三倍求前缀和，最后（单调队列 或 multiset）扫一遍求出链上的最大子段和。

Problem H

Unsolved.

Problem I

Solved by kblack. 00:26 (+1)

题意：求所有排列走法在路上距离总和。好像见到过原题。

题解：一共 $N!$ 个排列，每个排列提供 $N-1$ 条路径，显然每个路径的出现是对称的，所有每个点对一共走 $2(N-1)!$ 次，按边统计下一下就好了。

Problem J

Solved by ultmaster. 00:36 (+)

题意：有若干格点，格点上有积分，积分只有从 $(x-1,y-1)$ 走过去才能得到，求最高积分。

题解：把它想成一列一列的格子一起转移；按 $x$ 升序 $y$ 降序排，然后由于 $y$ 降序了，所以更新上面的东西并不会影响后面的。直接用一个线段树支持 set 标记和查询区间最大即可。