(mathcal{Description})
Link.
有 (n) 种颜色的，第 (i) 种有 (a_i) 个，任意两球互不相同。还有 (m) 个盒子，每个盒子可以被放入某些颜色的小球，且第 (i) 个盒子要求放入总数不少于 (b_i)。你要拿走尽量少的球，使得要求无法被满足，并求出此时拿球方案数模 (998244353) 的值。
(nle20)，(mle10^4)。
(mathcal{Solution})
如果保持清醒地做这道题还是比较简单的。
首先用 Hall 定理转化合法条件，记 (A={a_n})，(B={b_m})，(operatorname{adj}(Ssubseteq B)) 表示 (S) 内的 (b) 所邻接的 (a) 的并，则合法条件为
[forall Ssubseteq B,~sum_{bin S}blesum_{ainoperatorname{adj}(S)}a
]
那么可以得知非法条件。固定 (operatorname{adj}(S))，显然 (b) 能多选就多选，最终能得到最小取球数量为
[c=maxleft{0,min_{operatorname{adj}(S)}left{sum_{ainoperatorname{adj}(S)}a-sum_{operatorname{adj}({b})subseteqoperatorname{adj}(S)}b+1
ight}
ight}.
]
令集族 (mathcal S=arg min_{operatorname{adj}(S)}left{sum_{ainoperatorname{adj}(S)}a-sum_{operatorname{adj}({b})subseteqoperatorname{adj}(S)}b+1 ight})，也能避免算重地求出方案数为：
[sum_{Tsubseteq A}[exist Sin mathcal S,~Tsubseteq S]f(T,c).
]
其中 (f(T,c)) 表示在集合 (T) 内的 (a) 中一共选走 (c) 个，且每个 (a) 至少被选走一个的方案数，可以容斥计算。具体实现上，用几次 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
", way );
return 0;
}
(mathcal{Details})
某个问题无法找到解决方法时，尤其是在速度相关的比赛时，一定要冷静下来，形式地描述“我想要求什么东西”，而不是对着代码修修补补。