bzoj 4017 子序列和的异或以及异或的和

位运算很好的一个性质是可以单独每一位考虑。。。。。

题解请看：http://blog.csdn.net/skywalkert/article/details/45401245

对于异或的和，先枚举位，求所有异或和和中该位为1的有多少个，再乘以该位的大小（2的多少次方）。

即单独每一位考虑，每位带的权不一样。

对于和的异或，只需知道每一位中和的改位为1的奇偶性，就可以知道最终的异或值上该位是0还是1。

也是单独考虑每一位，看该位为0或1的条件。

 /**************************************************************

     Problem: 4017

     User: idy002

     Language: C++

     Result: Accepted

     Time:9896 ms

     Memory:3544 kb

 ****************************************************************/

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define N 100010

 #define Mod 998244353

 using namespace std;

 typedef long long dnt;

 int n;

 int aa[N];

 namespace Task1 {

     dnt ans;

     int cnt[];

     dnt mpow( dnt a, int b ) {

         dnt rt;

         for( rt=; b; b>>=,a=a*a%Mod )

             if( b& ) rt=rt*a % Mod;

         return rt;

     }

     void main() {

         for( int b=; b<=; b++ ) {

             cnt[] = cnt[] = ;

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

                 int bb = (aa[i]>>b)&;

                 int c0 = cnt[];

                 int c1 = cnt[];

                 cnt[^bb] = c0;

                 cnt[^bb] = c1;

                 cnt[bb]++;

                 ans = (ans+cnt[]*mpow(,b)) % Mod;

             }

         }

         printf( "%lld ", ans );

     }

 };

 namespace Task2 {

     dnt s[N];

     dnt disc[N], dtot;

     int bit[][N];

     dnt ans;

     void init() {

         memset( bit, , sizeof(bit) );

     }

     void modify( int bit[], int a, int delta ) {    //  a in [1,n]

         for( int i=a; i<=dtot; i+=i&-i )

             bit[i] += delta;

     }

     int query( int bit[], int a ) {

         int rt = ;

         for( int i=a; i; i-=i&-i )

             rt += bit[i];

         return rt;

     }

     void main() {

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

             s[i] = s[i-] + aa[i];

         for( int b=; b<=; b++ ) {

             dnt cnt = ;

             dnt mask = (1LL<<b) - ;

             dtot = ;

             disc[++dtot] = ;

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

                 disc[++dtot] = s[i] & mask;

             sort( disc+, disc++dtot );

             dtot = unique( disc+, disc++dtot ) - disc - ;

             init();

             modify( bit[], lower_bound(disc+,disc++dtot,)-disc, + );

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

                 dnt bmid = (s[i]>>b) & ;

                 dnt brgt = s[i] & mask;

                 int irgt = lower_bound( disc+, disc++dtot, brgt ) - disc;

                 if( bmid ) {

                     cnt += query( bit[], irgt );

                     cnt += query( bit[], dtot ) - query( bit[], irgt );

                 } else {

                     cnt += query( bit[], dtot ) - query( bit[], irgt );

                     cnt += query( bit[], irgt );

                 }

                 modify( bit[bmid], irgt, + );

             }

             ans |= (cnt&) ? (1LL<<b) : ;

         }

         printf( "%lld\n", ans );

     }

 };

 int main() {

     scanf( "%d", &n );

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

         scanf( "%d", aa+i );

     Task1::main();

     Task2::main();

 }

巴特西

bzoj 4017 子序列和的异或以及异或的和

最新文章

热门文章