#P5487. 【模板】Berlekamp–Massey 算法

    ID: 6233 远端评测题 4000ms 500MiB 尝试: 0 已通过: 0 难度: 7 上传者: 标签>O2优化线性递推Berlekamp-Massey(BM) 算法

【模板】Berlekamp–Massey 算法

题目背景

前置技能:线性递推 & BM\&~\rm BM 算法。

同时,请注意优化你的空间。保证最短递推式唯一

出题人为强行二合一感到很抱歉,但是其实也是可以学习一下 k2lognk^2 \log n 线性递推的——保证在 -O2 指令下可以过。

题目描述

给出一个数列 PP00 开始的前 nn 项。

求序列 PPmod 998244353\bmod~998244353 下的最短线性递推式,并在 mod 998244353\bmod~998244353 下输出 PmP_m

输入格式

第一行共两个数 n,mn,m ,表示将会给出序列 PP 的前 nn 项,要求 PmP_m

第二行 nn 个数,表示 P0,P1,P2,,Pn1P_0,P_1,P_2,\ldots,P_{n-1}

输出格式

第一行输出该最短线性递推式。

第二行输出 PmP_m 的值。

输入数据 1

4 10
1 1 2 3

输出数据 1

1 1 
89

输入数据 2

5 10
3 7 27 95 339

输出数据 2

3 2
691707

提示

对于 100%100 \% 的数据,n<m109n < m \le {10}^91n100001 \le n \le 10000,保证递推式最长不超过 50005000