← 返回题目列表

AtCoder · abc009_4

D. 递归公式

中文机器翻译题面 查看原题

問題文

数列 A 表示所有元素都是 它可以表示为 32 位的无符号整数,其值确定如下。

  • 简介 K 項 A_1,\,A_2,\,...,\,A_K 作为输入给出。 除了
  • A 除了 K 术语序列 C_1,\,C_2,\,...,\,C_K (此外,所有元素都是 32 位无符号整数)作为输入给出,K+1 项目之后 A 的值是这个 使用 C 计算如下。 对于
    • N ≧ 1 反对 A_{N+K} = (C_1\,和\,A_{N+K-1})\,异或\,(C_2\,和\,A_{N+K-2})\,异或\,...\, 异或\,(C_K\,和\,A_N)
    • 但是,AND 表示按位与,XOR 表示按位异或。

这个序列 A 的 M 第一个值 编写一个程序来查找 A_M 。


入力

输入是按以下格式从标准输入给出的。

K M
A_1 A_2 ... A_K
C_1 C_2 ... C_K
  • 1 行包含一个整数,表示在开始时确定的项数。 K (1 ≦ K ≦ 100)和一个表示序列中所需项数的整数 给出了 M (1 ≦ M ≦ 10^9)。
  • 2 编号顺序是 第一个 A 第一个 K 术语按顺序给出。A 的所有值 32 适合一位无符号整数。
  • 3 编号顺序是 第一个 A 的 K+1 计算项目后的项目时使用的编号规则 C 的元素按顺序给出。C 的所有值 32 适合一位无符号整数。

出力

A_M 的值 在 1 行输出。

还在输出末尾包含换行符。


入力例1

3 5
10 20 30
7 19 13

出力例1

16

实际上 计算 A 的值得出以下结果。

  • A_4 = (7\,和\,30)\,异或\,(19\,和\,20)\,异或\,(13\,和\,10) = 30
  • A_5 = (7\,和\,30)\,异或\,(19\,和\,30)\,异或\,(13\,和\,20) = 16

入力例2

5 100
2345678901 1001001001 3333333333 3141592653 1234567890
2147483648 2147483647 4294967295 4294967294 3434343434

出力例2

1067078691

入力例3

30 999999999
11627 5078 8394 6412 10346 3086 3933 668 9879 11739 4501 6108 12336 8771 2768 2438 2153 7047 5476 313 1264 369 12070 10743 10663 747 370 4671 5235 3439
114 3613 3271 5032 11241 6961 3628 150 12191 2396 7638 3046 11594 8162 11136 786 9878 2356 11660 1070 3649 10882 9746 1415 3307 7077 9319 9981 3437 544

出力例3

2148