网站如何建设与安全,重庆app软件制作公司,wordpress商城主题 原创,附近免费手工活拿回家题干#xff1a;
Rinne 最近学习了位运算相关的知识#xff0c;她想运用自己学习的知识发明一个加密算法。 首先她有一个源数组 A#xff0c;还有一个密钥数组 B#xff0c;现在她想生成加密后的数组 C。 她发明的方法是#xff1a;当计算CiCi的时候#xff0c;首先将…题干
Rinne 最近学习了位运算相关的知识她想运用自己学习的知识发明一个加密算法。 首先她有一个源数组 A还有一个密钥数组 B现在她想生成加密后的数组 C。 她发明的方法是当计算CiCi的时候首先将 CiCi 赋值为Ci−1Ci−1然后加上 AiAi 分别与每一个满足 j i 的 BjBj 异或后的和然后加上 BiBi 分别与每一个满足 j i 的 AjAj 异或后的和最后加上 AiAi 与 BiBi 的异或和。 形式化的讲关于 CiCi 的递推式为以下式子
C00C00
CiCi−1AixorBi(∑i−1j1(AixorBjAjxorBi))CiCi−1AixorBi(∑j1i−1(AixorBjAjxorBi))
现在她想用程序来实现这个过程你能帮帮她吗由于输出可能太大你只需要输出每个 CiCi 模 10971097的结果即可。
输入描述:
第一行一个整数 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
备注:
N≤105,ai≤109
解题报告 依据异或的性质统计前缀的每一位是1的数的个数是0的数的个数最后对于每一次查询直接调用这个前缀然后做一次异或就行了。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX 2e5 5;
const ll mod 1e97;
ll a[MAX],b[MAX],c[MAX];
ll A[33][2],B[33][2];
ll ans;
int main()
{int n;cinn;for(int i 1; in; i) scanf(%lld,ai);for(int i 1; in; i) scanf(%lld,bi);for(int i 1; in; i) {ans 0;ans (c[i-1] (a[i]^b[i]))%mod;for(int j 0; j33; j) {ans ((A[j][ !(b[i]j1) ] B[j][ !(a[i]j1) ])j)%mod;A[j][a[i]j1], B[j][b[i]j1];}c[i] ans%mod;}for(int i 1; in; i) printf(%lld%c,c[i],i n ? \n : );return 0 ;}总结 几个小地方以后寻找哪一位还是用右移这种吧因为与运算完了之后就是非零即一而不是非零即2^n。 还有啊异或运算的优先级低于运算所以那个ans的时候需要在 a[i]^b[i] 外面加括号。。 运用乘法原理也可以简单求出答案因为通过画图不难看出Ci其实就是A数组和B数组所有 非同一数组 的元素都进行过一次异或操作
AC代码2
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX 2e5 5;
const ll mod 1e97;
ll a[MAX],b[MAX],c[MAX];
ll A[33][2],B[33][2];
int main()
{int n;cinn;for(int i 1; in; i) scanf(%lld,ai);for(int i 1; in; i) scanf(%lld,bi);for(int i 1; in; i) {for(int j 0; j33; j) {A[j][a[i]j1], B[j][b[i]j1];c[i] ((A[j][0]*B[j][1]A[j][1]*B[j][0])j)%mod;}}for(int i 1; in; i) printf(%lld%c,c[i],i n ? \n : );return 0 ;}
写这份代码的时候傻了c[i]了直接应该是。。因为内层循环是要循环的啊、、又不是c[i]只算一遍。
