装备购买(线性基）

题目链接

https://www.acwing.com/problem/content/description/211/

算法：先贪心，然后高斯消元算出基底的个数

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=505;
#define PII pair<int,int>
const int INF=2e9; 
const int mod=1e9+7;
ll power(ll a,ll b)
{
    ll ans=1;
    for(;b;b>>=1)
    {
        if(b&1)
            ans=ans*a%mod;
        a=a*a%mod;
    }
    return ans;
}
ll inv(ll x)
{
    return power(x,mod-2);
}
struct hp{
    ll a[N];
    int val;
};
hp ma[N];
int b[N],n,m,cnt,ans;
int cmp(const hp &a,const hp &b)
{
    return a.val<b.val;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>ma[i].a[j];
            ma[i].a[j]%mod;
        }
    }
    for(int i=1;i<=n;i++)
    {
        cin>>ma[i].val;
    }
    sort(ma+1,ma+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(ma[i].a[j])
            {
                if(!b[j])
                {
                    b[j]=i;
                    ++cnt;
                    ans+=ma[i].val;
                    break;
                }
                else
                {
                    ll t=ma[i].a[j]*inv(ma[b[j]].a[j])%mod;
                    for(int k=j;k<=n;k++)
                    {
                        ma[i].a[k]=((ma[i].a[k]-ma[b[j]].a[k]*t%mod)%mod+mod)%mod;
                    }
                }
            }
        }
    }
    cout<<cnt<<" "<<ans<<"
";
    return 0;
 }