首页 > 代码库 > BZOJ 4004: [JLOI2015]装备购买 [高斯消元同余 线性基]

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

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

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

所有只好在模意义下做啦

只是巨慢无比

 

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <bitset>using namespace std;typedef long long ll;const int N=505;const int P=1e9+7;inline int read(){    char c=getchar();int x=0,f=1;    while(c<0||c>9){if(c==-)f=-1;c=getchar();}    while(c>=0&&c<=9){x=x*10+c-0;c=getchar();}    return x*f;}int n,m,c,ans,cnt;double eps=1e-8;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=1;    for(;b;b>>=1,a=a*a%P)        if(b&1) re=re*a%P;    return re;}inline ll Inv(ll a){return Pow(a,P-2);}bool check(Matrix &a){    for(int i=1;i<=m;i++) if(a[i]) return true;    return false;}int pivot[N];void Gauss(){    for(int i=1;i<=n;i++){        for(int j=1;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=1;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=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=read();    for(int i=1;i<=n;i++) a[i].c=read();    sort(a+1,a+1+n);    Gauss();    printf("%d %d",cnt,ans);}

 

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