bzoj3811 uoj36 玛里苟斯

做题前问了一下miaom，得到了一个奇怪的回答

mmp

这题分类讨论

k=1sb题

k=2按位计算，把每个数看成几个2的幂次的和，按位跑期望

k>2线性基sb题

没了

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define N 100005

 #define M 75

 #define ll unsigned long long

 using namespace std;

 int n,flag; ll ans,res,mod,bin[M],a[N],base[M]; bool f[M][M];

 void calc(){

     int i,j;

     for (i=; i<=n; i++)

         for (j=; j>=; j--) if (a[i]&bin[j])

             if (!base[j]){

                 base[j]=a[i]; break;

             } else a[i]^=base[j];

     for (j=n=; j<; j++) if (base[j]) a[++n]=base[j];

 }

 void solve1(){

     int i,j,k,t;

     for (i=; i<; i++)

         for (j=; j<=n; j++) f[i][j]=(a[j]&bin[i])?:;

     for (i=; i<; i++)

         for (j=; j<; j++){

             for (k=; k<=n; k++) if (f[i][k]) break;

             if (k>n) continue;

             for (k=; k<=n; k++) if (f[j][k]) break;

             if (k>n) continue;

             t=;

             for (k=; k<=n && !t; k++)

                 if (f[i][k]!=f[j][k]) t=;

             if (i+j--t<) res++; else ans+=bin[i+j--t];

             ans+=res>>; res&=;

         }

     printf("%llu",ans); puts(res?".5":"");

 }

 void dfs(int k,ll now){

     if (k>n){

         int i; ll u=,v=;

         for (i=; i<=flag; i++){

             u*=now; v*=now;

             u+=v>>n; v&=mod;

         }

         ans+=u; res+=v;

         ans+=res>>n; res&=mod;

         return;

     }

     dfs(k+,now); dfs(k+,now^a[k]);

 }

 void solve2(){

     mod=bin[n]-; dfs(,);

     printf("%llu",ans); puts(res?".5":"");

 }

 int main(){

     scanf("%d%d",&n,&flag); int i;

     bin[]=; for (i=; i<; i++) bin[i]=bin[i-]<<;

     for (i=; i<=n; i++) scanf("%llu",&a[i]);

     if (flag==){

         for (i=; i<=n; i++) ans|=a[i];

         printf("%llu",ans>>); puts((ans&)?".5":"");

         return ;

     }

     calc();

     if (flag==) solve1(); else solve2();

     return ;

 }