orz deco,哈希新知识get
Solution [COCI2017-2018#3] Dojave
题目大意:给定一长为(n)的(0-(2^n-1))的全排列,问有多少个连续子序列可以通过交换任意两个数使得其异或和为(2^n-1)
哈希
分析:
首先不考虑限制有(frac{n imes (n+1)}{2})个连续子序列,正难则反,我们考虑有多少个连续子序列不合法
一段连续子序列不合法的充要条件是这段连续子序列的长度是(4)的倍数并且连续子序列里面的数两两异或为(2 ^ n-1)
证明:
设(S)为一段区间异或和,(t)为(S;xor;(2^n-1)),定义如果(x,y)配对有(x;xor;y=t)
长为奇数一定合法,你一定找得到一个元素,和它配对的元素在区间外
长为偶数,如果有数字没有配对一定合法
如果有奇数个配对,不妨设有(3)对
则(S=t;xor;t;xor;t=t=S;xor;(2^n-1)),不存在
那么如果长为(4)的倍数并且两两配对,那么不合法
所以不合法的只有长为(4)倍数并且两两配对的,这个可以用哈希来做
我们认为如果一段长为(4)倍数的区间异或和为(0)那么两两配对,但是这样容易被卡
可以将一个数以及和它配对的那个数都换成一个很大的随机数,然后再用双哈希就可以保证正确性了
长为(2)有两对,注意特判
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <map>
using namespace std;
typedef long long ll;
const int maxn = 23;
inline int read(){
int x = 0;char c = getchar();
while(!isdigit(c))c = getchar();
while(isdigit(c))x = x * 10 + c - '0',c = getchar();
return x;
}
map<pair<int,int>,int> mp[4];
int n,inf,val[1 << maxn],sum[1 << maxn][2],pos[1 << maxn];
long long ans;
int main(){
n = 1 << read(),inf = n - 1;
if(n == 2)return puts("2"),0;
for(int i = 1;i <= n;i++)val[i] = read(),pos[val[i]] = i;
for(int i = 1;i <= n;i++){
sum[i][0] = sum[pos[val[i] ^ inf]][0] = rand() | rand() << 15;
sum[i][1] = sum[pos[val[i] ^ inf]][1] = rand() | rand() << 15;
}
for(int i = 1;i <= n;i++)sum[i][0] ^= sum[i - 1][0],sum[i][1] ^= sum[i - 1][1];
ans = (long long)n * (n + 1) >> 1;
mp[0][make_pair(0,0)] = 1;
for(int i = 1;i <= n;i++){
int opt = i % 4;
pair<int,int> pai = make_pair(sum[i][0],sum[i][1]);
ans -= mp[opt][pai];
mp[opt][pai]++;
}
printf("%lld
",ans);
return 0;
}