第 5 场算法季度赛

题目：

5.精准难度【算法赛】 - 蓝桥云课

问题描述

小蓝，蓝桥杯命题组的核心人物。今年的他出题灵感爆发，一口气出了 N 道题目，难度系数分别为 A1,A2,…,AN。

只是，这些题目的难度参差不齐，让组委会专家们伤透了脑筋。如何客观地评估这套题目的整体难度呢？

为了更精准地评估这些题目的整体难度，专家组发明了一种计算方式：

首先，找出所有连续的子序列，并计算每个子序列中所有难度系数的乘积。
然后，将每个子序列的乘积对 2025 取余。
最后，将所有取余后的结果进行异或运算。

最终得到的异或和，就是这 N 道题目的“精准难度”。

现在，请你帮助小蓝，计算出这 N 道题目的“精准难度”。

输入格式

第一行包含一个整数 N (1≤N≤105)，表示题目的数量。

第二行包含 N 个正整数 A1,A2,…,AN (1≤Ai≤105)，表示每道题目的难度系数。

输出格式

输出一个整数，表示这 N 道题目的“精准难度”。

样例输入

3
2 2 3

样例输出

运行限制

语言	最大运行时间	最大运行内存
C++	1s	256M
C	1s	256M
Java	2s	256M
Python3	3s	256M
PyPy3	3s	256M
Go	3s	256M
JavaScript	3s	256M

总通过次数: 25 | 总提交次数: 166 | 通过率: 15.1%

思路：

使用两个for循环硬算肯定是超时的，所以我们使用动态规划来递推。首先我们需要知道0是异或的恒等元（0^2 = 2）。其次我举例子{1,2,3}

按理说答案是这样计算的。我们该如何递推呢？我们都知道，每一次加入新元素，就会多出很多个集合需要求。我以cnt = 0；

第一个元素1，有{1}.

第二个元素2加入，有{1,2}，{2}.

第三个元素3加入，有{1,2,3}，{2,3}，{3}

假设都会自动取模，我就不说取模了。

结合我画的图以及数学知识{1,2,3}，这个集合的乘积是3*（2*1），{2,3}这个集合的乘积是3*（2）

说明我们可以保存先前的子序列的乘积，留到后面新元素继续使用，避免重复计算了。

但是有人可能会问，如何保存先前的子序列呢？换句话说，请你再次看一遍我画的图，答案是什么？发现所有连续子序列乘积最后都会变成一个数字相互异或。（废话也是重点）

{1,2}的乘积是2，{2}的乘积也是2，新加入元素3有三个集合，除去{3}其中两个的集合，{1,2,3}的乘积是6，{2,3}的乘积是6.。我们可以发现新元素直接对上一次储存的乘积相乘，加上{3}的乘积3.就是序列{1,2,3}的所有子序列出现的乘积。例如（6,6,3）。……

我们可以用一个数组储存所有的子序列出现的乘积，相当于哈希表。因为2^2 = 0。0^2 = 2。表里面是偶数次数的可以不用计算异或。大大减少了计算次数。

我的代码有三个集合， ansA，ansB，ans2。

用下标储存出现过子序列的乘积，值是出现的次数。

ansB是储存最终答案数组，将出现过的所有子序列的所有乘积以哈希表的形式存入数组。

ansA是for循环里面的数组，意味着每次更新元素都要被重置，它作为一个间接数组，储存的是新元素和迭代数组ans2的关系的更新。

ans2是作为一个迭代数组，储存的是上一次所有元素子序列的乘积，也是哈希表形式的储存方式。

我将模拟一遍，让我们更好理解。{2,3,4}序列

输入：

2 3 4

对2进行取模，ansA[2]++,ansB[2]++。其实是{2}

第一个循环，遍历结束都没有用到，因为此时ans2都是空的。

将ansA 赋值个ans2。ansA被清0.此时ans2[2] = 1.

对3进行取模，ansA[3]++,ansB[3]++。其实是{3}

此时ansA[3] = 1。ans2[2] = 1。

进入for循环，因为（2）是出现过的乘积。现在需要ansA和ans2进行配合，求出新的元素加入后的序列的所有子序列的乘积。

y = (3*2)%MOD,其实就是{2,3}

ansA[6] = ansA[6] + ans2[2]。这里的意思是，乘积为6的组合为总个数+可以跟新元素3形成连续的子序列个数。（假设有三个乘积为2的子序列，可以跟新元素3组成的连续子序列，那么不就是存在3个连续子序列吗？所以是本身组合为6的次数+原来乘积为2出现的次数，ansA【6】 = 0 + 3。在这题是ansA【6】 = 0 + 1）

这个循环结束，此时ansA[6] = 1；

将ansA 赋值个ans2。ansA被清0.此时ans2[6] = 1，ans2[2] = 1.

到这里其实已经足够了.现在可以发现，数组将子序列最终的乘积以下标的形式储存，并且值是出现的个数。新元素的加入产生新的连续子序列就是将新元素乘以上一次子序列乘积，就是每一个连续子序列的乘积。有人可能还没有完全理解，会认为会出现不连续也相乘的情况，其实是不会的。数组ansA每次都会赋值给ans2.ans2储存的只会是上一次连续的子序列。和新元素产生的子序列的乘积仍然是连续的子序列。

代码如下：

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const int MOD = 2025;
vector<ll> ans2(MOD + 10, 0); 
vector<ll> ansB(MOD + 10, 0);
int main()
 {
    ll n;
    cin >> n;
    for (ll i = 1; i <= n; i++) 
	{
        vector<ll> ansA(MOD + 10, 0); 
        ll x;
        cin >> x; 
        ll Q = x % MOD; 
        ansA[Q]++; 
        ansB[Q]++; 
        for (ll j = 0; j < MOD; j++)
		{
			if(ans2[j] > 0) 
			{
				ll y = (j * x) % MOD; 
	            ansA[y] = ansA[y] + ans2[j];
	            ansB[y] = ansB[y] + ans2[j]; 		
			}
        }
        ans2 = ansA;
    }
    ll ans = 0;
    for (ll i = 0; i < MOD; i++) 
	{
        if (ansB[i] % 2 != 0) 
        ans ^= i; 
    }

    cout << ans << endl;
    return 0;
}