BZOJ 2844 albus就是要第一个出场 ——高斯消元线性基-白红宇

BZOJ 2844 albus就是要第一个出场 ——高斯消元线性基

阅读量：6864 次

发布时间：2019-06-26

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

【题目分析】

高斯消元求线性基。

题目本身不难，但是两种维护线性基的方法引起了我的思考。

void gauss(){    k=n;    F(i,1,n){        F(j,i+1,n) if (a[j]>a[i]) swap(a[i],a[j]);        if (!a[i]) {k=i-1; break;}        D(j,30,0) if (a[i]>>j & 1){            b[i]=j;            F(x,1,n) if (x!=i && a[x]>>j&1) a[x]^=a[i];            break;        }    }}

　　——高斯消元求线性基

for (int i=1;i<=n;++i)        for (int j=31;j>=0;--j)        if ((a[i]>>j)&1){            if (!lb[j]) {lb[j]=a[i]; cnt++; break;}            else a[i]^=lb[j];        }

　　——动态维护线性基

不会高斯消元解Xor方程组的我，直接使用了第二种方式求解，发现直接WA飞了。

（后来一想，居然过了样例）。

那么他们有什么差别呢。

我对拍了许多组，发现他们求出的线性基的大小是相同的。

但是高斯消元的线性基有一个神奇的特征，是使得该位为1的最小的数。（最小的）

那么有必要去写高斯消元吗？

显然不必要，做一个小操作就好了。

于是改了改动态维护线性基的代码，成了这个样子 ↓

for (int i=1;i<=n;++i)        for (int j=31;j>=0;--j)        if ((a[i]>>j)&1){            if (!lb[j]) {lb[j]=a[i]; cnt++; break;}            else a[i]^=lb[j];        }    for (int i=31;i>=0;--i)        if (lb[i])            for (int j=i-1;j>=0;--j)                if ((lb[i]>>j)&1) lb[i]^=lb[j];

　　——改版

神奇的AC了。线性基与高斯消元的结果相同。

考虑时间复杂度，都是log*n的，自然没什么差别，但是用哪种就是仁者见仁智者见智了。

实际上高斯消元会快一些（达不到复杂度上限），而动态维护线性基是标准的上限（雾）

【代码】

#include 
     
      #include 
      
       #include 
       
        #include 
        
          #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                using namespace std; #define maxn 100005#define ll long longint read(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9') {if (ch=='-') f=-1; ch=getchar();} while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f;} const int mod=10086;int n,cnt=0,q;int lb[34],a[maxn]; int power(int a,int b){// printf ("Pow %d ^ %d is ",a,b); int ret=1; while (b) { if (b&1) (ret*=a)%=mod; (a*=a)%=mod; b>>=1; }// printf("%d\n",ret); return ret;} bool cmp(int a,int b){ return a>b;} int main(){ n=read(); for (int i=1;i<=n;++i) a[i]=read();// sort(a+1,a+n+1);// for (int i=1;i<=n;++i) cout<
                
                 <<" "; cout<
                 
                  =0;--j) if ((a[i]>>j)&1){ if (!lb[j]) {lb[j]=a[i]; cnt++; break;} else a[i]^=lb[j]; } for (int i=31;i>=0;--i) if (lb[i]) for (int j=i-1;j>=0;--j) if ((lb[i]>>j)&1) lb[i]^=lb[j];// printf("The Xor Base is %d\n",cnt); int rk=0,x=0,tmp=0; for (int j=31;j>=0;--j) if (lb[j]){ tmp++;// cout<
                  
                   <<":"<
                   
                    <
                    
                     q) continue; x^=lb[j];// printf("now add %d\n",cnt-tmp); rk=(rk+power(2,cnt-tmp))%mod; } for (int i=1;i<=n-cnt;++i) rk=(rk*2)%mod; rk++; cout<
                     
                      <

转载于:https://www.cnblogs.com/SfailSth/p/6220328.html

你可能感兴趣的文章