【BZOJ 4004】[JLOI2015] 装备购买

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4004
数据生成器:http://paste.ubuntu.com/23209631/

这个题目,看一眼,就是要求一组花费最小的线性基
第一次写,写的整数高斯消元,发现爆了long long
第二次改成double,发现精度不够
第三次,搞成整数高斯消元+MOD,遂过之
想一想,如果不用线性基,只是求一组线性基的话,MOD确实没影响

另外网上用double写的标程全部被叉掉了,不要问我是怎么知道的 qwq
1248545547

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 500+9;
const int MOD = 1000000007;
 
int n,m,f[N][N],bas[N],cost[N],num[N],cnt,vout; 
 
inline int read(){char c=getchar(); int ret=0,f=1;while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}return ret*f;} 
inline bool cmp(const int a, const int b) {return cost[a] < cost[b];}
 
inline void update(int w) {
    for (int i=1;i<=m;i++) if (f[w][i]) {
        if (!bas[i]) {bas[i] = w, cnt++, vout += cost[w]; break;}
        else {
        	int t2 = f[bas[i]][i], t1 = f[w][i];
            for (int j=1;j<=m;j++) f[w][j] = ((LL)f[w][j]*t2 - (LL)f[bas[i]][j]*t1) % MOD;
        }
    }
}
 
int main(){
    n = read(); m = read();
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) f[i][j] = read();
    for (int i=1;i<=n;i++) cost[i] = read(), num[i] = i;
    sort(num+1,num+1+n,cmp);
    for (int i=1;i<=n;i++) update(num[i]);
    printf("%d %d\n",cnt,vout);
    return 0;
}