[清华集训 2014] 玛里苟斯

UOJ #36.

思路

case1

当$k=1$时,我们可以很方便地分开统计每一个二进制位对于答案的贡献,所以分开统计就好了。考虑所有数的第$i$个二进制位,如果有一个数的第$i$个二进制位是$1$的话,那么很显然,包含奇数个此位是$1$的数的子集和包含偶数个此为是$1$的数的子集的数量是相等的,要证明的话从组合的角度证一下就好了,所以答案就是$$\frac{a_1|a_2|\dots |a_n}{2}$$

case2

当$k=2$时,可以考虑把平方拆一下。考虑有一个数,其第$i$个二进制位是$b_i$,那么它的平方就可以写为$$\sum \limits_{i}\sum \limits_{j}2^{i+j}\cdot b_i\cdot b_j$$。我们就可以考虑分别枚举$i$和$j$,求出对于每个$i$和$j$的$d_i\cdot d_j$的期望。

case3

当$k\geq3$时,因为答案保证不超过$2^{63}$,所以每个数就一定不超过$2^{\frac{63}{k}}$,那么线性基的大小也最多只有$\frac{63}{k}<22$,那么就很舒服了,$O(2^{\frac{63}{k}})$枚举选哪些线性基就可以了

代码

#include <iostream>
#include <cstdio>
#include <vector>

template <typename T> void in(T &_){
    char c=getchar(); _=0; int fl=1;
    while(c<'0'||c>'9') fl=c=='-'?-1:fl, c=getchar();
    while(c>='0'&&c<='9') _=_*10+c-'0', c=getchar(); _*=fl;
}

typedef unsigned long long LL;
int N, K;
LL a[100010];

namespace Sub1{
    void main(){
        LL ans=0;
        for(int i=1; i<=N; i++) ans|=a[i];
        printf("%llu", ans>>1);
        puts((ans&1)?".5":"");
    }
}

namespace Sub2{
    void main(){
        LL ans=0, res=0;
        for(int i=0; i<63; i++)
            for(int j=0; j<63; j++){
                bool fl=false;
                for(int k=1; k<=N; k++) if((a[k]>>i)&1) fl=true;
                if(!fl) continue;
                fl=false;
                for(int k=1; k<=N; k++) if((a[k]>>j)&1) fl=true;
                if(!fl) continue;
                fl=false;
                for(int k=1; k<=N; k++) if(((a[k]>>i)&1)^((a[k]>>j)&1)) fl=true;
                if(i+j-1-(fl?1:0)<0) res++;
                else ans+=1ULL<<(i+j-1-(fl?1:0));
            }
        ans+=res>>1; res&=1;
        printf("%llu", ans);
        puts(res?".5":"");
    }
}

namespace Sub3{
    int siz;
    LL ans, res, p[65];
    std::vector<std::pair<LL, int> > vec;
    #define mp std::make_pair

    void insert(LL x){
        for(int i=62; ~i; i--) if((x>>i)&1){
            if(p[i]) x^=p[i];
            else{p[i]=x; vec.push_back(mp(x, i)); siz++; break;}
        }
    }

    void main(){
        for(int i=1; i<=N; i++) insert(a[i]);
        for(int i=0; i<(1<<siz); i++){
            LL val=0;
            for(int j=0; j<vec.size(); j++) if((i>>j)&1)
                val^=vec[j].first;
            LL a=0, b=1;
            for(int j=0; j<K; j++) a*=val, b*=val, a+=b>>siz, b&=(1ULL<<siz)-1;
            ans+=a, res+=b, ans+=res>>siz, res&=(1ULL<<siz)-1;
        }
        printf("%llu", ans);
        puts(res?".5":"");
    }
}

int main(){
    in(N); in(K);
    for(int i=1; i<=N; i++) in(a[i]);
    if(K==1) Sub1::main();
    else if(K==2) Sub2::main();
    else Sub3::main();
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注