小团有一个序列a ,下标从1 开始直到n ,分别为 。现在,小团定义了以下式子:
现在小团想让小美回答
的值
其中, 代表异或运算
请你帮助小美。
小提示:
现在小团想让小美回答
的值
其中, 代表异或运算
小提示:
输入第一行包含一个整数n,表示序列a的长度。接下来一行n个数,空格隔开,第i个数表示
输出包含一个数,即的值
2 3 2
0
对于40%的数据,对于100%的数据,
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 )
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); } }
//参考大佬题解,知道要优化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; }
根据 零葬题解给出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