2018 CCPC Online Contest

oxx

Problem A

Solved by dreamcloud.

题意：

题解：

Problem B

Unsolved.

题意：

题解：

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.

题意：

题解：

Problem J

Solved by dreamcloud.

题意：

题解：

ECNU Foreigners

Problem A

Solved by kblack. 00:49 (+)

Problem B

Unsolved.

Problem C

Solved by zerol. 00:50 (+)

Problem D

Solved by zerol. 00:29 (+)

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)

Problem H

Unsolved.

Problem I

Solved by kblack. 00:26 (+1)

Problem J

Solved by ultmaster. 00:36 (+)

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

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