我要招人

去企业版

首页 > 试题广场 >

式子求值

[编程题]式子求值

热度指数：1356 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小团有一个序列a ，下标从1 开始直到n ，分别为 $a_1, a_2, ..., a_n$ 。现在，小团定义了以下式子： $b_i=a_i\oplus \oplus_{j=1}^{n}(i\ mod\ j)$

现在小团想让小美回答

$\oplus_{i=1}^{n}(b_i)$ 的值

其中， $\oplus$ 代表异或运算

请你帮助小美。

小提示： $b_i=a_i\oplus\oplus_{j=1}^n\left(i\;mod\;j\right)=a_i\oplus\left(i\;mod\;1\right)\oplus\left(i\;mod\;2\right)\oplus\left(i\;mod\;3\right)\ldots.\oplus\left(i\;mod\;n\right)$

输入描述:

输入第一行包含一个整数n，表示序列a的长度。
接下来一行n个数，空格隔开，第i个数表示

输出描述:

输出包含一个数，即 $\oplus_{i=1}^n\left(b_i\right)$ 的值

示例1

输入

2
3 2

输出

说明

备注:

对于40%的数据，
对于100%的数据，

算法知识视频讲解

柠致

js版本，不知道为啥只通过一个测试用例，有大佬看看没

var str = readline()
var str1 = readline()
var n = parseInt(str.trim())
var a = str1.trim().split(' ')
var res = 0
var multi = [0]  // multi[i]表示0^1^2^...^i

for(var i=1; i<=n; i++) {
    res = res ^ parseInt(a[i-1])
    multi[i] = multi[i-1] ^ i
}

// 找出（i%j）这个方形矩阵（N * N）的规律
for(var i=1; i<=n; i++) {
    if((n/i)%2 == 0) {
        res = res ^ multi[n%i]
    } else {
        res = res ^ multi[i-1] ^ multi[n%i]
    }
}

console.log( res )

发表于 2021-08-15 21:03:03 回复(0)

yuzu_9497

n=int(input())
arr=list(map(int,input().split()))
a=0
dp=[0]*(n+1)
x=0
for i in range(n):
    a=a^arr[i]
    dp[i+1]=dp[i]^(i+1)
    if (n//(i+1))%2==0:
        pass
    else:
        x^=dp[i]
    x^=dp[n%(i+1)]
print(a^x)

发表于 2021-04-27 11:53:50 回复(0)

pein531

首先我们要明白一个事实，一个数和0进行异或就是它本身，而一个数和自己异或就是0。很显然，异或操作是满***换律的，题目要求我们计算的式子一定包含所有的 a_i 进行异或，那不妨在输入数组 a 的时候先把这个值算出来，这样我们就只剩下一堆余数要异或了。

写一个遍历程序看一下这些余数 i % j 有什么规律：

主对角线及其以上的规律很明显，我们再观察一下主对角线及其以上的这个模式在一列中能重复多少遍。对于第i列，主对角线及其以上的元素有i个，所以这个模式能重复n/i次。如果这个值为偶数，那这些0~i-1的循环异或完肯定就为0了，剩下的n%i个数再异或就得到这一列的异或结果；假如这个值为奇数，那么之前出现的偶数次0~i-1的循环异或完就为0了，还余下一次0~i-1的异或和1~n%i的异或，它两再异或就得到了这一列的异或结果。因此得到如下规律：

(1) 如果 n / i 为偶数，异或结果为1^2^...^(n%i)。

(2) 如果 n / i 为奇数，异或结果为1^2^...^(n%i)^0^1^2^...^(i-1)。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String[] strA = br.readLine().trim().split(" ");
        int[] a = new int[n + 1];
        int[] multi = new int[n + 1];    // multi[i]表示0^1^2^...^i
        int res = 0;
        // 先把所有的a[i]进行异或
        for(int i = 1; i <= n; i++) {
            a[i] = Integer.parseInt(strA[i - 1]);
            res ^= a[i];
            multi[i] = multi[i - 1]^i;
        }
        for(int i = 1; i <= n; i++){
            if((n/i) % 2 == 0)
                res ^= multi[n % i];
            else
                res ^= multi[n % i] ^ multi[i - 1];
        }
        System.out.println(res);
    }
}

编辑于 2021-03-03 00:01:08 回复(10)

努力进大厂的萌新

//参考大佬题解，知道要优化mod矩阵，自己也写了几个，没找出规律，大意了，可以用计算机生成，然后找规律
//应该更方便一点，加油！！！
#include<bits/stdc++.h>

using namespace std;

const int N =100007;
int nums[N];
int multi[N];

int main(){
    int n;
    cin >> n;
    
    for(int i = 1 ;i <= n;i++){
        multi[i] = multi[i - 1] ^ i;
        cin >> nums[i];
    }
    int ans = 0;
    /*
    for(int i = 1 ;i <= n; i++){
        for(int j = 1 ;j <= n;j++){
            ans ^= i % j;
        }
    }*/
 /*
(1) 如果 n / i 为偶数，异或结果为1^2^...^(n%i)。
(2) 如果 n / i 为奇数，异或结果为1^2^...^(n%i)^0^1^2^...^(i-1)。*/
    for(int i = 1 ;i <= n;i++){
        if((n / i ) & 1){
            ans ^= multi[n% i] ^ multi[i - 1];
        }else{
            ans ^= multi[n % i];
        }
    }
    
    for(int i = 1; i <= n;i++){
        ans ^= nums[i];
    }
    cout << ans <<endl;
    return 0;
}

发表于 2022-04-05 20:37:49 回复(0)

Python

DownUp子

根据零葬题解给出Python版本
重点在于：

因此得到如下规律：
(1) 如果 n / i 为偶数，异或结果为1^2^...^(n%i)。
(2) 如果 n / i 为奇数，异或结果为1^2^...^(n%i)^0^1^2^...^(i-1)。

然后预先计算出前缀和就可以降低时间复杂度。

while True:
    try:
        n = int(input())
        nums = [int(i) for i in input().split()]
        ans = 0

        # 计算前缀和
        pre = [0] * (n + 1)
        for i in range(1, n + 1):
            pre[i] = pre[i - 1] ^ i

        for i in range(1, n + 1):
            ans ^= nums[i - 1] # ai 部分计算进去
            if (n / i) % 2 == 0: # 异或结果规律的运用
                ans ^= pre[n % i]
            else:
                ans ^= pre[n % i] ^ pre[i - 1]

        print(ans)
    except:
        break

发表于 2021-08-14 15:48:56 回复(2)