CF1586 f1 f2 Korney Korneevich and XOR 思维+dp
题目链接
题意：
给出长度为n的数组a，对于数组的严格递增子序列，计其异或和为xor_sum,输出所有能得到的所有xor_sum，并输出集合大小。
easy version： 1≤n≤1e5, 0≤a[i]≤500
hard version： 1≤n≤1e6, 0≤a[i]≤5000
做法：
先提一嘴这题的easy version，由于a[i]很小，我们可以使用滚动数组，dp[i]为以递增子序列异或和为i时，结尾的最小值，tp[i]则作为临时数组暂存结果，转移方程为 tp[j^x] = min(tp[j^x],x)
根据异或的特性，我们空间开a[i]最大值的两倍，时间复杂度1e8，代码如下
int dp[N],tp[N];
int main() {
int n; cin>>n;
for(int i=0;i<=1000;i++) dp[i] = 114514;
dp[0] = 0;
for(int i=1;i<=n;i++){
int x; cin>>x;
for(int j=0;j<=1000;j++) tp[j] = dp[j];
for(int j=0;j<=1000;j++) if(x>dp[j]) tp[j^x] = min(tp[j^x],x);
for(int j=0;j<=1000;j++) dp[j] = tp[j];
}
vector<int> ans;
for(int i=0;i<=1000;i++) if(dp[i]!=114514) ans.push_back(i);
cout<<ans.size()<<le;
for(auto i: ans) cout<<i<<" ";
cout<<le;
return 0;
}
接下来讲讲hard version怎么优化，计maxn = 10000,也就是a[i]最大值的两倍。
- 假设某一递增序列的异或和为
nxt，且此时它以x结尾，那么它能贡献给[x+1,maxn] - 假设现在又得到一段异或和为
nxt，但是以x+1为结尾，那么他能贡献给[x+2,maxn] - 这就约等于重复计算了两遍，为了避免重复贡献，我们可以在一开始定义
a[nxt] = maxn,令这个数最多贡献maxn次，有以x结尾的时候就把a[nxt] = x,并把贡献加给[x+1,maxn],再次算到以x+1结尾的时候由于a[nxt] < x就不会重复计算了。 - 我们定以vector
pos[maxn],用来存递增区间的异或和，保证区间的最后一个数小于i - 对于每个异或和结果，最多转移maxn次，因此复杂度为 maxn*maxn = 1e8
代码：
#define fst std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout << std::fixed << std::setprecision(20)
#define le "\n"
#define ll long long
#include <bits/stdc++.h>
using namespace std;
const int N=1e4+50;
const int mod=998244353;
vector<int> pos[N]; //递增区间的异或和，区间的最后一个数小于i
int a[N],ans[N]; //a数组记录最多贡献次数
int main() {
fst;
int n; cin>>n;
for(int i=0;i<=10000;i++){
pos[i].push_back(0);
a[i] = 10000;
}
for(int i=1;i<=n;i++){
int x; cin>>x;
for(auto i: pos[x]){
int nxt = i^x;
ans[nxt] = 1;
while(a[nxt]>x){
a[nxt]--;
if(a[nxt]!=x) pos[a[nxt]].push_back(nxt);
}
}
pos[x].clear();
}
int cnt = 0;
ans[0] = 1;
for(int i=0;i<=10000;i++) cnt += ans[i];
cout<<cnt<<le;
for(int i=0;i<=10000;i++) if(ans[i]) cout<<i<<" ";
return 0;
}