首页 > 试题广场 >

Rinne Loves Xor

[编程题]Rinne Loves Xor

时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

Rinne 最近学习了位运算相关的知识，她想运用自己学习的知识发明一个加密算法。
首先她有一个源数组 A，还有一个密钥数组 B，现在她想生成加密后的数组 C。
她发明的方法是：当计算 $C_i$ 的时候，首先将 $C_i$ 赋值为 $C_{i-1}$ ，然后加上 $A_i$ 分别与每一个满足 j < i 的 $B_j$ 异或后的和，然后加上 $B_i$ 分别与每一个满足 j < i 的 $A_j$ 异或后的和，最后加上 $A_i$ 与 $B_i$ 的异或和。
形式化的讲，关于 $C_i$ 的递推式为以下式子：

$C_i = C_{i-1} + A_i xor B_i + (\sum_{j=1}^{i-1} (A_i xor B_j + A_j xor B_i))$

现在她想用程序来实现这个过程，你能帮帮她吗？由于输出可能太大，你只需要输出每个 $C_i$ 模

的结果即可。

输入描述:

第一行一个整数 N，表示数组 A 和 B 的长度。
第二行 N 个整数表示数组 A。
第三行 N 个整数表示数组 B。

输出描述:

输出一行 N 个整数，表示加密后的数组 C。

示例1

输入

10
65605 70259 77306 43823 61443 98602 9261 7662 46394 83019
81393 5966 61479 24259 92528 96132 35859 47981 11702 71736

输出

15796 166270 623824 1132402 1650729 2445262 3256941 4150718 5106184 6353038

备注:

算法知识视频讲解

Kur1su

发表于 2020-05-01 14:47:05

Solution 挺简单的一道题, 虽然带着异或的皮, 看起来很复杂, 但其实只要我们从二进制位考虑就不难了因为题目所给的数据是因此二进制位上最多也就位, , 我们考虑能否有的做法观察递推式前面两个可以完成不用管重点是后面那个累加式子, 我们把它们拆开其实也就是从贡献方面考虑, 展开全文

sunrise__sunrise

发表于 2020-04-29 00:45:17

Solution 题目大意：给定两个序列a，b；那么答案序列c，就是当前位置前一项c的值，加上比当前位置小的j，对应数组分别异或a[i]和b[i]，累加的和。可以画图举个栗子体会一下。如果觉得我再胡说八道可以自己理解理解题面如果直接模拟。。O(N^2)炸的理所当然，那么就要想想别的路子。通过题面展开全文

回归梦想

发表于 2020-05-01 21:46:11

链接：https://ac.nowcoder.com/acm/contest/5505/B来源：牛客网时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld 题目描述输入描述:第一行一个整数 N，表示数组展开全文

问题信息

思维题

难度：

0条回答 0收藏 18浏览

Rinne Loves Xor

输入描述:

输出描述:

输入

输出

备注:

问题信息

热门推荐

相关试题