2018-2019 Winter Petrozavodsk Camp, Oleksandr Kulkov Contest 1

Problem A

Unsolved.

Problem B

Unsolved.

Problem C

Unsolved.

Problem D

Solved by zerol. 01:27 (+1)

题意：已知一个 k 项的线性递推式，要求一组 $c_i$，使得 $f_n = \sum_{i=1}^k c_i f_{n - b_i}$ 与之等效，其中 $b_i$ 已知。

题解：令 D 是一个很大的数，用 $f_{n-D}, f_{n-D-1}, \dots, f_{n-D-k+1}$ 的线性组合来表示 $f_n$，对于给定的递推式，那么系数已知，对于需要填充参数的递推式，每一个系数都是 $c_i$ 的线性组合，那么得到了一个线性方程组，由于数据的随机性，那么可以认为这个方程是满秩的，可以方便得得到解。其中求线性组合的系数需要用到多项式快速幂（是线性递推求某一项的加速算法中的一部分，复杂度是 $O(\log n \cdot k^2)$），解方程就是最方便的那种高斯消元。

zerol: 我的自主研发板子有一个漏洞，就是不支持一项的递推，会 RE（已经坑了我两次了）。这次因此以十几秒的差距错失了一血。

Problem E

Solved by zerol. 00:14 (+)

温暖的伪装成博弈的签到。

Problem F

Unsolved. (-3)

Problem G

Unsolved.

Problem H

Solved by ultmaster. 01:45 (+1)

Problem I

Unsolved.

Problem J

Unsolved.

Problem K

Solved by kblack. 00:18 (+)