/ FWOJ / 题库 /

扩展斐波那契1

扩展斐波那契1

背景

定义函数\(F_n(x)\)如下:

\[F_n(x)=\begin{cases}f_x&(x\leq n)\\a_1F_n(x-1)+a_2F_n(x-2)+...+a_nF_n(x-n)&(x>n)\\\end{cases}\]

其中\(n\)和\(x\)为正整数。

描述

输入\(x\),\(n\),\(f_i\)和\(a_i\),求\(F_n(x)\)的值。

由于结果可能很大,求出\(F_n(x)\)%\(65537\)的值即可。

格式

输入格式

三行。
第一行为两个正整数\(x\)和\(n\)。
第二行有\(n\)个自然数\(f_i\)。
第三行有\(n\)个自然数\(a_i\)。

\(1\leq x,n\leq 10^5\)
\(0\leq f_i,a_i\leq 10^5\)

输出格式

一行,\(F_n(x)\)%\(65537\)的值。

样例

样例输入

4 2
1 2
1 1

样例输出

5

限制

内存256MB,每个测试点1s。

信息

ID
1040
难度
9
分类
(无)
标签
递交数
1
已通过
1
通过率
100%
上传者

相关

在下列训练计划中:

FWOJ题目分类