AT_abc009_4.[ABC009D] 漸化式

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

数列 $A$ 的所有元素均可用 $32$ 位无符号整数表示，其值按如下方式确定。

前 $K$ 项 $A_1,\,A_2,\,...,\,A_K$ 由输入给出。
另有一个长度为 $K$ $K$ 的数列 $C_1,\,C_2,\,...,\,C_K$ $C_{1}, C_{2}, ..., C_{K}$ （所有元素也均为 $32$ $32$ 位无符号整数），输入给出。 $A$ $A$ 的第 $K+1$ $K + 1$ 项及之后的项用该 $C$ $C$ 数列按如下方式计算：
- 对于 $N \geq 1$ ，有 $A_{N+K} = (C_1\,\text{AND}\,A_{N+K-1})\,\text{XOR}\,(C_2\,\text{AND}\,A_{N+K-2})\,\text{XOR}\,\ldots\,\text{XOR}\,(C_K\,\text{AND}\,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 \leq K \leq 100$ ）和 $M$ （要求的项的编号， $1 \leq M \leq 10^9$ ）。
第 $2$ 行依次给出数列 $A$ 的前 $K$ 项。 $A$ 的所有值均为 $32$ 位无符号整数。
第 $3$ 行依次给出用于计算 $A$ 的第 $K+1$ 项及之后项的数列 $C$ 的 $K$ 个元素。 $C$ 的所有值均为 $32$ 位无符号整数。

输出格式

输出 $A_M$ 的值，占一行。

输出末尾需换行。

输入输出样例

输入#1
```
3 5
10 20 30
7 19 13
```
输出#1
```
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

说明/提示

样例解释 1

实际计算 $A$ 的各项如下：

$A_4 = (7\,\text{AND}\,30)\,\text{XOR}\,(19\,\text{AND}\,20)\,\text{XOR}\,(13\,\text{AND}\,10) = 30$
$A_5 = (7\,\text{AND}\,30)\,\text{XOR}\,(19\,\text{AND}\,30)\,\text{XOR}\,(13\,\text{AND}\,20) = 16$

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页