哎这个题 WA 了无数遍。。。果然人太弱。。。
首先我们把这些装备按照花费从小到大排序，然后依次考虑是否能买这个装备。
至于这样为什么是对的，好像有一个叫拟阵的东西可以证明，然而我不会。TATQAQ
至于怎么考虑是否能买这个装备呢，我们可以动态更新线性基，具体操作：
- 对当前向量进行高斯消元，注意要从从高位往低位消。
- 如果消元完毕后当前向量变成了 $0$ 向量，那么我们就可以用之前的装备凑出当前装备，否则就不能凑出来。
每次更新线性基需要 $O(m^2)$ 的时间，要更新 $O(n)$ 次。
时间复杂度 $O(nm^2)$，稍微优化一下应该可以过吧。。。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
#define N 500 + 5
#define Mod 998244353 int n, m, tot, ans;
int Ord[N], W[N]; struct Node
{
int num[N];
Node () {memset(num, , sizeof(num));}
inline void init()
{
for (int i = ; i <= m; i ++)
scanf("%d", num + i);
}
inline bool operator < (const Node a) const
{
for (int i = ; i <= m; i ++)
{
if (num[i] != && !a.num[i]) return ;
else if (!num[i] && a.num[i] != ) return ;
}
return ;
}
}A[N], P[N]; inline int power(int u, int v)
{
int res = ;
for (; v; v >>= )
{
if (v & ) res = (LL) res * u % Mod;
u = (LL) u * u % Mod;
}
return res;
} inline bool cmp(int u, int v)
{
return W[u] < W[v];
} inline bool All_zero(int id)
{
for (int i = ; i <= m; i ++)
if (A[id].num[i] != ) return ;
return ;
} inline int Inc(int a, int b)
{
return a + b - (a + b >= Mod ? Mod : );
} inline bool Modify(int id)
{
if (tot == m) return ;
if (!tot)
{
tot ++;
for (int i = ; i <= m; i ++)
P[tot].num[i] = A[id].num[i];
return ;
}
for (int d = ; d <= tot; d ++)
{
int i = ;
for (; i <= m; i ++)
if (P[d].num[i] != ) break ;
if (!A[id].num[i]) continue ;
int mul = (LL) A[id].num[i] * power(P[d].num[i], Mod - ) % Mod;
for (i = ; i <= m; i ++)
A[id].num[i] = Inc(A[id].num[i], Mod - ((LL) P[d].num[i] * mul % Mod));
}
bool ok = ;
for (int i = ; !ok && i <= m; i ++)
if (A[id].num[i] != ) ok = ;
if (!ok) return ;
tot ++;
for (int i = ; i <= m; i ++)
P[tot].num[i] = A[id].num[i];
for (int d = tot; d > ; d --)
{
if (P[d - ] < P[d])
{
for (int i = ; i <= m; i ++)
swap(P[d - ].num[i], P[d].num[i]);
}
else break ;
}
return ;
} int main()
{
#ifndef ONLINE_JUDGE
freopen("4004.in", "r", stdin);
freopen("4004.out", "w", stdout);
#endif scanf("%d%d", &n, &m);
for (int i = ; i <= n; i ++)
A[i].init();
for (int i = ; i <= n; Ord[i] = i ++)
scanf("%d", W + i);
sort(Ord + , Ord + n + , cmp);
for (int i = ; i <= n; i ++)
{
int _i = Ord[i];
if (All_zero(_i)) continue ;
if (Modify(_i)) ans += W[_i];
}
if (!tot) ans = W[Ord[]], tot = ;
printf("%d %d\n", tot, ans); #ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
#endif
return ;
}
4004_Gromah