Difference between revisions of "2018-2019 Winter Petrozavodsk Camp, Oleksandr Kulkov Contest 1"
Jump to navigation
Jump to search
Line 18: | Line 18: | ||
题解:令 D 是一个很大的数,用 $f_{n-D}, f_{n-D-1}, \dots, f_{n-D-k+1}$ 的线性组合来表示 $f_n$,对于给定的递推式,那么系数已知,对于需要填充参数的递推式,每一个系数都是 $c_i$ 的线性组合,那么得到了一个线性方程组,由于数据的随机性,那么可以认为这个方程是满秩的,可以方便得得到解。其中求线性组合的系数需要用到多项式快速幂(是线性递推求某一项的加速算法中的一部分,复杂度是 $O(\log n \cdot k^2)$),解方程就是最方便的那种高斯消元。 | 题解:令 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 == | == Problem E == |
Revision as of 13:15, 13 March 2019
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 (+)