首页 > 代码库 > 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]装备购买 [高斯消元同余 线性基]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。