633E Binary Table-白红宇

633E Binary Table

阅读量：6240 次

发布时间：2019-06-22

本文共 696 字，大约阅读时间需要 2 分钟。

分析

我们发现n特别小，所以可以从这里入手

我们记录出所有列中某一种状态的列有多少个

我们再记录出每种列最少有多少个1(原来的1的个数和取反后的个数去最小值)

于是我们可以得出对于所有列异或一个数的答案

(实际就是对于每一行有一个全异或1或不异或的操作，将所有行压起来)

于是我们不难得到式子$Ans_i = \sum a_j * b_{j^i}$

直接fwt即可

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   using namespace std;#define int long longstring s[25];int a[2000000],b[2000000],n,m,N;inline void fwt(int a[],int f){ int i,j,k; for(i=1;i
                   
                    <<=1) for(j=0;j
                    
                     <<1)) for(k=0;k
                     
                      >s[i]; for(i=0;i
                      
                       >1]+(i&1); for(i=0;i