题目大意
见题面。
思路
本来以为zcx、pxj变强了，后来发现是SPJ出问题了。。。考试的时候感觉有点人均啊。。。结果自己还是只想出来一半。
我们假设 (f(x)=(lfloorfrac{2x}{2^n} floor+2x)pmod{2^n})，那么我们可以看出 (f(x)) 实际上就是 (x) 把第一位提到最后一位，那么我们就可以想到 (f(aotimes b)=f(a)otimes f(b))（虽然我考试的时候就是这里没有想到）。
考虑原问题，我们不难看出，答案就是：
[max_{x=0}^{2^n-1}{min_{i=0}^{m}f(xotimes ext{pre}(i))otimes ext{suf}(i+1)}
]
[=max_{x=0}^{2^n-1}{min_{i=0}^{m}f(x)otimes f( ext{pre}(i))otimes ext{suf}(i+1)}
]
然后我们把 (f( ext{pre}(i))otimes ext{suf}(i+1)) 放到 trie 树上面跑 dfs 就好了。
时间复杂度 (Theta(nm)) 。
( exttt{Code})
#include <bits/stdc++.h>
using namespace std;
#define Int register int
#define MAXN 100005
template <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 ('
'),write (res),putchar ('
');
return 0;
}