Difference between revisions of "2018 CCPC Online Contest"

From EOJ Wiki
Jump to navigation Jump to search
Line 52: Line 52:
 
== Problem G ==
 
== Problem G ==
  
Unsolved.
+
Unsolved(-5).
  
 
题意:
 
题意:

Revision as of 13:59, 25 August 2018

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

Unsolved(-5).

题意:

题解:

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 标记和查询区间最大即可。