题目传送门

题目大意

见题面。

思路

本来以为zcx、pxj变强了，后来发现是SPJ出问题了。。。考试的时候感觉有点人均啊。。。结果自己还是只想出来一半。

我们假设 \(f(x)=(\lfloor\frac{2x}{2^n}\rfloor+2x)\pmod{2^n}\)，那么我们可以看出 \(f(x)\) 实际上就是 \(x\) 把第一位提到最后一位，那么我们就可以想到 \(f(a\otimes b)=f(a)\otimes f(b)\)（虽然我考试的时候就是这里没有想到）。

考虑原问题，我们不难看出，答案就是：

\[\max_{x=0}^{2^n-1}\{\min_{i=0}^{m}f(x\otimes\text{pre}(i))\otimes \text{suf}(i+1)\}
\]\[=\max_{x=0}^{2^n-1}\{\min_{i=0}^{m}f(x)\otimes f(\text{pre}(i))\otimes \text{suf}(i+1)\}
\]

然后我们把 \(f(\text{pre}(i))\otimes \text{suf}(i+1)\) 放到 trie 树上面跑 dfs 就好了。

时间复杂度 \(\Theta(nm)\) 。

\(\texttt{Code}\)

#include <bits/stdc++.h>
using namespace std;#define Int register int
#define MAXN 100005template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}int n,m,a[MAXN],suf[MAXN],pre[MAXN];int f (int x){return (x * 2 + (x * 2) / (1 << n)) % (1 << n);}int cnt = 1,ch[MAXN * 30][2];void ins (int x){
int now = 1;
for (Int i = n - 1;~i;-- i){
int k = x >> i & 1;
if (!ch[now][k]) ch[now][k] = ++ cnt;
now = ch[now][k];
}
}int dp[MAXN * 30];int dfs (int now,int len){
if (len < 0) return 0;
if (dp[now]) return dp[now];
int res = 0;
if (!ch[now][1] && ch[now][0]) res = dfs (ch[now][0],len - 1) + (1 << len);
else if (!ch[now][0] && ch[now][1]) res = dfs (ch[now][1],len - 1) + (1 << len);
else{
res = max (res,dfs (ch[now][0],len - 1));
res = max (res,dfs (ch[now][1],len - 1));
}
return dp[now] = res;
}int query (int now,int len,int s){
if (len < 0) return 0;
int k = s >> len & 1;
if (ch[now][k]) return query (ch[now][k],len - 1,s);
else return query (ch[now][!k],len - 1,s) + (1 << len);
}unordered_map <int,bool> vis;signed main(){
read (n,m);
for (Int i = 1;i <= m;++ i) read (a[i]),pre[i] = pre[i - 1] ^ f (a[i]);
for (Int i = m;i >= 1;-- i)suf[i] = suf[i + 1] ^ a[i];
for (Int i = 0;i <= m;++ i) ins (pre[i] ^ suf[i + 1]);
int ans = dfs (1,n - 1),res = 0;
for (Int i = 0;i <= m;++ i){
int stx = ans ^ pre[i] ^ suf[i + 1];
if (!vis[stx] && query (1,n - 1,stx) == ans) vis[stx] = 1,res ++;
}
write (ans),putchar ('\n'),write (res),putchar ('\n');
return 0;
}