\(\mathcal{Description}\)
??Link.
??有 \(n\) 种颜色的，第 \(i\) 种有 \(a_i\) 个，任意两球互不相同。还有 \(m\) 个盒子，每个盒子可以被放入某些颜色的小球，且第 \(i\) 个盒子要求放入总数不少于 \(b_i\)。你要拿走尽量少的球，使得要求无法被满足，并求出此时拿球方案数模 \(998244353\) 的值。
??\(n\le20\)，\(m\le10^4\)。
\(\mathcal{Solution}\)
??如果保持清醒地做这道题还是比较简单的。
??首先用 Hall 定理转化合法条件，记 \(A=\{a_n\}\)，\(B=\{b_m\}\)，\(\operatorname{adj}(S\subseteq B)\) 表示 \(S\) 内的 \(b\) 所邻接的 \(a\) 的并，则合法条件为
\[\forall S\subseteq B,~\sum_{b\in S}b\le\sum_{a\in\operatorname{adj}(S)}a
\]
那么可以得知非法条件。固定 \(\operatorname{adj}(S)\)，显然 \(b\) 能多选就多选，最终能得到最小取球数量为
\[c=\max\left\{0,\min_{\operatorname{adj}(S)}\left\{\sum_{a\in\operatorname{adj}(S)}a-\sum_{\operatorname{adj}(\{b\})\subseteq\operatorname{adj}(S)}b+1\right\}\right\}.
\]
??令 \(\mathcal S=\arg \min_{\operatorname{adj}(S)}\left\{\sum_{a\in\operatorname{adj}(S)}a-\sum_{\operatorname{adj}(\{b\})\subseteq\operatorname{adj}(S)}b+1\right\}\)，也能避免算重地求出方案数为：
\[\sum_{T\in \mathcal S}\binom{\sum_{a\in T}a}{c}.
\]
具体实现上，用几次 FWT 即可。复杂度 \(\mathcal O(nm+2^nn)\)。
\(\mathcal{Code}\)
/*~Rainybunny~*/
#include <cstdio>
#define rep( i, l, r ) for ( int i = l, rep##i = r; i <= rep##i; ++i )
#define per( i, r, l ) for ( int i = r, per##i = l; i >= per##i; --i )
inline void chkmin( int& a, const int b ) { b < a && ( a = b ); }
const int MAXN = 20, MAXM = 1e4, MAXV = 2e6, MOD = 998244353;
int n, m, a[MAXN + 5], b[MAXM + 5], adj[MAXM + 5], sum[1 << MAXN];
int fac[MAXV + 5], ifac[MAXV + 5], tot[1 << MAXN];
int cvr[1 << MAXN], chs[1 << MAXN];
inline void subeq( int& a, const int b ) { ( a -= b ) < 0 && ( a += MOD ); }
inline int sub( int a, const int b ) { return ( a -= b ) < 0 ? a + MOD : a; }
inline int mul( const long long a, const int b ) { return int( a * b % MOD ); }
inline int add( int a, const int b ) { return ( a += b ) < MOD ? a : a - MOD; }
inline void addeq( int& a, const int b ) { ( a += b ) >= MOD && ( a -= MOD ); }
inline int mpow( int a, int b ) {
int ret = 1;
for ( ; b; a = mul( a, a ), b >>= 1 ) ret = mul( ret, b & 1 ? a : 1 );
return ret;
}
inline void init( const int s ) {
fac[0] = 1;
rep ( i, 1, s ) fac[i] = mul( i, fac[i - 1] );
ifac[s] = mpow( fac[s], MOD - 2 );
per ( i, s - 1, 0 ) ifac[i] = mul( ifac[i + 1], i + 1 );
}
inline int comb( const int a, const int b ) {
return a < b ? 0 : mul( fac[a], mul( ifac[b], ifac[a - b] ) );
}
inline void fwtAND( const int len, int* u, const auto& adf ) {
for ( int stp = 1; stp < len; stp <<= 1 ) {
for ( int i = 0; i < len; i += stp << 1 ) {
rep ( j, i, i + stp - 1 ) {
adf( u[j], u[j + stp] );
}
}
}
}
inline void fwtOR( const int len, int* u, const auto& adf ) {
for ( int stp = 1; stp < len; stp <<= 1 ) {
for ( int i = 0; i < len; i += stp << 1 ) {
rep ( j, i, i + stp - 1 ) {
adf( u[j + stp], u[j] );
}
}
}
}
int main() {
scanf( "%d %d", &n, &m );
rep ( i, 0, n - 1 ) scanf( "%d", &a[i] );
rep ( i, 0, m - 1 ) scanf( "%d", &b[i] );
rep ( i, 0, n - 1 ) {
rep ( j, 0, m - 1 ) {
int t; scanf( "%d", &t );
adj[j] |= t << i;
}
}
rep ( i, 0, m - 1 ) sum[adj[i]] += b[i];
fwtOR( 1 << n, sum, []( int& u, const int v ) { u += v; } );
int tak = 1e9;
rep ( S, 1, ( 1 << n ) - 1 ) {
rep ( i, 0, n - 1 ) if ( S >> i & 1 ) tot[S] += a[i];
if ( sum[S] ) chkmin( tak, tot[S] + 1 - sum[S] );
}
if ( tak <= 0 ) return puts( "0 1" ), 0;
printf( "%d ", tak );
int way = 0; init( tot[( 1 << n ) - 1] );
rep ( S, 1, ( 1 << n ) - 1 ) {
cvr[S] = tot[S] + 1 - sum[S] == tak;
chs[S] = comb( tot[S], tak );
if ( __builtin_popcount( S ) & 1 ) chs[S] = sub( 0, chs[S] );
}
fwtAND( 1 << n, cvr, []( int& u, const int v ) { u += v; } );
fwtOR( 1 << n, chs, addeq );
rep ( S, 1, ( 1 << n ) - 1 ) if ( cvr[S] ) {
( __builtin_popcount( S ) & 1 ? subeq : addeq )( way, chs[S] );
}
printf( "%d\n", way );
return 0;
}
\(\mathcal{Details}\)
??某个问题无法找到解决方法时，尤其是在速度相关的比赛时，一定要冷静下来，形式地描述“我想要求什么东西”，而不是对着代码修修补补。