南外Day16-高斯消元&线性基

A. 高斯消元

如题，这是一个喜欢卡精度的模板

cin.tie(0);cout.tie(0);cin>>n>>m;
for(int i=1;i<=m;i++)
for(int j=1;j<=n+1;j++)
    cin>>f[i][j];
for(int i=1;i<=n;i++){
    id=0;
    for(int j=1;j<=m;j++)
    if(ABS(f[j][i])>ABS(f[id][i]))
        id=j;
    if(ABS(f[id][i])>1e-10){
        for(int j=1;j<=n+1;j++)
            swap(f[i][j],f[id][j]);
    }else{continue;}
    for(int j=n+1;j>=i;j--) f[i][j]/=f[i][i];
    for(int j=1;j<=m;j++){
        if(j==i) continue;
        db fx=f[j][i]/f[i][i];
        for(int k=i;k<=n+1;k++)
            f[j][k]-=fx*f[i][k]; 
    }
}
for(int j=1;j<=m;j++){
    int tot=0;
    for(int i=1;i<=n;i++) if(ABS(f[j][i])<=1e-10) tot++;
    if(tot==n && ABS(f[j][n+1])>1e-10){
        cout<<"No solutions\n";
        return 0;
    }
}
for(int j=1;j<=n;j++)
    if(ABS(f[j][j])<=1e-10){
        cout<<"Many solutions\n";
        return 0;
    }
for(int i=1;i<=n;i++)
    cout<<int(f[i][n+1]/f[i][i]+0.5)<<"\n";

B. 球形空间产生器sphere

相较于A题只是改动了建图

cin.tie(0);cout.tie(0);cin>>n;
for(int i=1;i<=n+1;i++)
for(int j=1;j<=n;j++){
    cin>>x[i][j];
    x[n+2][j]=x[1][j];
}
for(int i=1;i<=n+1;i++)
for(int j=1;j<=n;j++){
    f[i][j]=2*(x[i+1][j]-x[i][j]);
    f[i][n+1]-=(x[i][j]*x[i][j]-x[i+1][j]*x[i+1][j]);
}m=n+1;

C. 前往小卖部 & D. 完全平方数 & E. 有趣的游戏

前面的题目以后再来探索吧

F. 线性基1

这是一个一个一个一个模板
这个代码长度真的是泰裤啦

void insert(int x){
    for(int i=50;i>=0;i--){
        if((x>>i)&1){
            if(!f[i]){f[i]=x;break;}
            x^=f[i];
        }
    }
}
signed main(){
    cin.tie(0);cout.tie(0);cin>>n;
    for(int i=1;i<=n;i++){
        cin>>m;
        insert(m);
    }
    for(int i=50;i>=0;i--){
        if((k^f[i])>=k)
            k^=f[i];
    }
    cout<<k;
    return 0;
} 

G. 线性基2

这仍然是一个一个一个一个模板啊啊啊啊

for(int i=dm;i;i--){
for(int j=i-1;j>=0;j--){
    if((f[i]>>j)&1)
        f[i]^=f[j];
}}
for(int i=0;i<=dm;i++)
if(f[i]) a[k++]=f[i];cin>>q;
while(q--){
    cin>>m;res=0;
    if(k!=n) m--;
    if(m>=(1ll<<k)){cout<<"-1\n";continue;}
    for(int i=0;i<k;i++){
        if(m&1) res^=a[i];
        m>>=1;
    }
    cout<<res<<&#039;\n&#039;;
}

H. 线性基3

本题原名：albus就是要第一个出场
然后可恶的张超赛时改了题目

k=1;
while(res--){
    k<<=1;
    k%=mod;
}cin>>n;res=0;m=1;
for(int i=0;i<=dm;i++,n>>=1){
    if(!f[i]) continue;
    if(n&1) res+=m;
    m<<=1;
}
cout<<((res%mod)*k+1ll)%mod;

I. 幸运数字 & J. shallot

前面的题目，以后也探索不了