bzoj 2844 子集异或和名次

感谢：

http://blog.sina.cn/dpool/blog/s/blog_76f6777d0101d0mr.html

的讲解（特别是2^(n-m)的说明）。

 /**************************************************************
     Problem: 2844
     User: idy002
     Language: C++
     Result: Accepted
     Time:308 ms
     Memory:2052 kb
 ****************************************************************/ #include <cstdio>
 #include <iostream>
 #define Mod 10086
 #define N 100010
 using namespace std; int n, m, q;
 int aa[N], bit[N]; void gauss() {
     int i=;
     for( int b=; b>=; b-- ) {
         for( int j=i; j<n; j++ )
             if( (aa[j]>>b)& ) {
                 swap( aa[j], aa[i] );
                 break;
             }
         if( (aa[i]>>b)& ) {
             for( int j=i+; j<n; j++ )
                 if( (aa[j]>>b)& )
                     aa[j] ^= aa[i];
             bit[i] = b;
             i++;
         }
     }
     m = i;
     for( int i=; i<m; i++ )
         for( int j=i-; j>=; j-- )
             if( (aa[j]>>bit[i])& )
                 aa[j] ^= aa[i];
 }
 int mpow( int a, int b ) {
     int rt;
     for( rt=; b; b>>=,a=(a*a)%Mod )
         if( b& ) rt=(rt*a)%Mod;
     return rt;
 }
 int main() {
     scanf( "%d", &n );
     for( int i=; i<n; i++ )
         scanf( "%d", aa+i );
     scanf( "%d", &q );
     gauss();
     int cur = ;
     int rank = (q==?:);
     for( int i=; i<m; i++ ) {
         if( (cur^aa[i])<q ) {
             cur ^= aa[i];
             rank = (rank + (<<(m--i))%Mod) % Mod;
         }
     }
     rank = (rank*mpow(,n-m)+) % Mod;
     printf( "%d\n", rank );
 }