COCI. Dojave

dojave(4s256M)

给定一个正整数M,和0到2^M-1共2^M个数的排列，计算机先选择一段连续的子串，你必须选两个不同的元素出来，交换它们的位置，使得计算机选出来的子串在交换后的元素的异或值为2^M-1,如果可以，你将获胜。现在请你统计有多少种不同的选法，你可以获胜。

输入：

第一行一个正整数M(1 ≤ M ≤ 20)

接下来是一行，是0到2^M-1 的排列，用空格隔开。

输出：

一行一个数，表示可以获胜的方法总数。

50%的数据1 ≤ M ≤ 14

SAMPLE TESTS

input

0 1 2 3

Output

题目大意：

给定一段序列2^M个数的排列，有多少种方案可以满足最多交换一次使区间异或和为2^M-1

分析：

记前缀异或和为S,ed=1<<M
那么区间异或和为t=S[R]^S[L-1]
我们记t^g=ed-1
g=a[A]^a[B](A,B分别为区间内和外的两个数)
因为给的是个全排列
所以对于给定的g
任何一个数C都有D与之异或为g(唯一匹配)

区间个数为奇数：
所以如果所选区间个数为奇数
那么肯定会一个数C落单便可以和区间外的D进行交换
那么就肯定可以获胜

区间个数为偶数:
如果所选区间个数为偶数
有数没配对：
如果其中有数没有匹配那么它也可以和区间外的D交换
最后肯定会获胜

所以数配对：
会产生len/2个g

如果g的个数为奇数
那么t=g g^g=ed-1
这是不可能的因为两相同的数异或为0

所以只要g个数为偶数的情况不获胜
那么t=0 g=ed-1
所以区间长度要为4的倍数

求解：

确定了g
我们就两两配对了
我们为了确保知晓两两配对
哈希一下
记录个前缀和确保出现A 只要出现B才会异或为0

我们再开4个map
1 2 3 4 5 6 7
因为6只有可能从2来
记录一下当前异或和如果之前有相同的异或值说明这之间异或和为0
这样我们就确保了长度为4的倍数并且两两配对

用总的方案数减去这些不合法的方案数得到答案

附上代码：

#include<bits/stdc++.h>
using namespace std;
const int N=(1<<20)+12;
int M,ed;
int id[N],a[N],t[N][2];

int rand() {static int seed=703;return seed=1LL*seed*48271LL%0x7fffffff;}
map<pair<int,int>,int> st[4];
int main()
{
    freopen("dojave.in","r",stdin);
    freopen("dojave.out","w",stdout);
    scanf("%d",&M);ed=1<<M;
    long long ans=1LL*(1+ed)*ed/2;
    for(int i=1;i<=ed;i++) scanf("%d",&a[i]),id[a[i]]=i;
    for(int i=0;i<ed/2;i++) 
    {
        t[id[i]][0]=rand();t[id[i]][1]=rand();
        t[id[(ed-1)^i]][0]=t[id[i]][0];
        t[id[(ed-1)^i]][1]=t[id[i]][1];
    }
    for(int i=1;i<=ed;i++) t[i][0]^=t[i-1][0],t[i][1]^=t[i-1][1];
    for(int i=0;i<=ed;i++) 
    {
        ans-=st[i%4][make_pair(t[i][0],t[i][1])];
        st[i%4][make_pair(t[i][0],t[i][1])]++; 
    }
    if(M==1) ans=2;
    printf("%lld
",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

View Code