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) k^2)$),解方程就是最方便的那种高斯消元。
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 (+)