BZOJ 4004: [JLOI2015]装备购买 [高斯消元同余 线性基]

时间：2023-12-12 22:17:56

和前两(一)题一样,不过不是异或方程组了.....

然后bzoj的新数据是用来卡精度的吧.....

所有只好在模意义下做啦

只是巨慢无比

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <bitset>

using namespace std;

typedef long long ll;

const int N=;

const int P=1e9+;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,m,c,ans,cnt;

double eps=1e-;

struct Matrix{

    ll a[N];

    int c;

    ll& operator[](int x){return a[x];}

    bool operator <(const Matrix &r)const{return c<r.c;}

}a[N];

inline ll Pow(ll a,int b){

    ll re=;

    for(;b;b>>=,a=a*a%P)

        if(b&) re=re*a%P;

    return re;

}

inline ll Inv(ll a){return Pow(a,P-);}

bool check(Matrix &a){

    for(int i=;i<=m;i++) if(a[i]) return true;

    return false;

}

int pivot[N];

void Gauss(){

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

        for(int j=;j<=m;j++) if(a[i][j]){

            if(pivot[j]){

                int pj=pivot[j];

                ll t=a[i][j]*Inv(a[pj][j])%P;

                for(int k=;k<=m;k++) a[i][k]=(a[i][k]-t*a[pj][k]%P+P)%P;

            }else{pivot[j]=i;break;}

        }

        if(check(a[i])) ans+=a[i].c,cnt++;

    }

}

int main(){

    freopen("in","r",stdin);

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++) for(int j=;j<=m;j++) a[i][j]=read();

    for(int i=;i<=n;i++) a[i].c=read();

    sort(a+,a++n);

    Gauss();

    printf("%d %d",cnt,ans);

}

相关文章