33OJ
登录 注册

#P5678. [GZOI2017] 河神

    ID: 6439 远端评测题 1000ms 256MiB 尝试: 0 已通过: 0 显示难度提高 上传者: 标签>数学2017各省省选O2优化贵州矩阵乘法

[GZOI2017] 河神

背景

GZOI2017 D2T1

终于忍受不了苦 X 的搬砖生活, Shlw 把手里的板砖扔进了河里.

不出意料地, 河神冒了出来.

Shlw 说: “我掉了金砖, 快给我金砖!”

“!!! 你已经知道套路了吗,”河神说道, “但是你要金砖的话, 我就不给你2017 彩虹小马大电影的资源了哦. 如果你说实话的话, 我还可以考虑一下.”

Shlw 发现事情并不简单, 在金钱和信仰面前, 难以抉择.

突然, Shlw 不理会河神, 自顾自的地跑走了.

“唉, 现在的年轻人啊... 真不知道在想什么.”Pinkie Pie 感叹, 卸下了河神伪装.

题目描述

Shlw 从河神给的选择中,获得了一道当年挂掉的代数题的灵感。

但现在他希望你来帮忙解答,因为他自己忙着去搜小马资源去了。

给出数列 {an}\{a_n\} 和 {bn}\{b_n\} 以及 {An}\{A_n\} 的递推关系,试求出数列 {An}\{A_n\} 第 NN 项。

递推关系为:

$$A_n=\begin{cases}a_n & 0 \le n < K \\ \bigoplus_{0 \le t < K} (A_{n-K+t} \otimes b_t) & n \ge K \end{cases}$$

其中,⊗\otimes 表示与操作,⊕\oplus 表示或操作。

输入格式

第一行两个正整数 NN 和 KK。

第二行 KK 个空格隔开的非负整数,表示 {an}\{a_n\}。

第三行 KK 个空格隔开的非负整数,表示 {bn}\{b_n\}。

输出格式

一行,一个整数,表示{An}\{A_n\}。

10 5
2 3 5 7 12
23 45 2 4 8
15

提示

【样例解释】

从 A0A_0 至 A10A_{10} 分别为:2,3,5,7,12,15,15,13,15,15,152, 3, 5, 7, 12, 15, 15, 13, 15, 15, 15。

【数据约束】

测试点编号 NN KK 其他限制
11 ≤104\le10^4 ≤100\le100 无
22 ≤109\le10^9 =1=1 ^
3∼53\sim5 ≤106\le10^6 ≤10\le10 an,bn<2a_n,b_n<2
6,76,7 ≤108\le10^8 ≤15\le15 无
8∼108\sim10 ≤109\le10^9 ≤100\le100 ^

对于 100%100\% 的数据,N≤109,K≤100,0≤an,bn≤263−1N\le10^9,K\le100,0\le a_n,b_n\le 2^{63}-1。

【后记】

后来,Pinkie Pie 偷偷来到 Shlw 家里,她把这题拿回去考 Apple Jack,于是 Apple Jack 就有了狂吃苹果来畅游多重宇宙的本领。