式子求值

[编程题]式子求值

热度指数：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%的数据，

算法知识视频讲解

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)