0x35 高斯消元与线性空间

颓了十天回来做题果然……

感觉还是很有收获的，这两以前都没学过

bzoj1013: [JSOI2008]球形空间产生器sphere

poj1830(upd)

之前做得很烂还被 D飞*2 了。。重做一次

对于一个灯，把能把它点亮的其他灯设为1，然后高斯消元。

注意在这里的系数只是一个判断的手段，判断是否受到影响，并不是参与运算的（之前纠结了很久）

用二进制状压判断无解多解比较方便。（之前直接判当前位是不是0直接break错的一逼）

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;

int n,q[1100];
void guess()
{
    for(int j=1;j<=n;j++)
    {
        for(int i=j+1;i<=n;i++)
            if(q[i]>q[j])swap(q[i],q[j]);
        if(q[j]<=1)    
        {
                 if(q[j]==0)printf("%d
", (1<<(n-j+1)) );
            else if(q[j]==1)printf("Oh,it's impossible~!!
");
            return ;
        }
        
        int z;
        for(int i=n;i>=1;i--)
            if(q[j]&(1<<i)){z=i;break;}
        for(int i=1;i<=n;i++)
        {
            if(i==j)continue;
            if(q[i]&(1<<z))q[i]^=q[j];
        }
    }
    printf("1
");
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int x,y;
        scanf("%d",&n);
        memset(q,0,sizeof(q));
        for(int i=1;i<=n;i++)scanf("%d",&x),q[i]^=x;
        for(int i=1;i<=n;i++)scanf("%d",&x),q[i]^=x;
        for(int i=1;i<=n;i++)q[i]|=(1<<i);
        while(scanf("%d%d",&x,&y)!=EOF)
        {
            if(x==0&&y==0)break;
            q[y]|=(1<<x);
        }
        guess();
    }
    return 0;
}

bzoj4004: [JLOI2015]装备购买

hdu3949(upd):没开LL见祖宗系列（记得是1LL<<i啊）
裸的线性基，但是求第k大的时候稍微注意下，求第k大的时候实际上求的是第k+1大，因为0会被看作第0大的……而且0需要特判存不存在，假如存在那么k--，否则这里就和前面的多算抵消了

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
typedef unsigned long long uLL;

uLL lt[110],zero;
void insert(uLL x)
{
    for(int i=63;i>=0;i--)
        if(x&(1LL<<i))
        {
            if(lt[i]==0){lt[i]=x;return ;}
            else x^=lt[i];
        }
    zero=1;
}
int plen;uLL p[110];
void rebuild()
{
    for(int i=63;i>=0;i--)
        if(lt[i]>0)
        {
            for(int j=i-1;j>=0;j--)
                if(lt[i]&(1LL<<j))lt[i]^=lt[j];
        }
    plen=0;
    for(int i=0;i<=63;i++)
        if(lt[i]>0)p[++plen]=lt[i];
}
void findkth(uLL x)
{
    if(x>=(1LL<<plen)){printf("-1
");return ;}
    uLL ans=0;
    for(int i=plen;i>=1;i--)
        if(x&(1LL<<i-1))ans^=p[i];
    printf("%I64u
",ans);
}

int main()
{
    int T,T_T=0;
    scanf("%d",&T);
    while(T--)
    {
        int n;uLL x;
        scanf("%d",&n); zero=0;
        memset(lt,0,sizeof(lt));
        for(int i=1;i<=n;i++)
            scanf("%I64u",&x), insert(x);
        rebuild();
        
        int Q;
        scanf("%d",&Q);
        printf("Case #%d:
",++T_T);
        while(Q--)
        {
            scanf("%I64u",&x);x-=zero;
            findkth(x);
        }
    }
    return 0;
}