为了更好的阅读体验，请点击这里
题目链接：G – Electric Circuit
看到了 \(N\) 的数据范围，因此是显然的状压 dp。
不妨设 \(f_S\) 为仅使用 \(S\) 集合中的所有点，能够连成恰好 \(1\) 个连通块的方案数。\(g_S\) 为仅使用 \(S\) 集合中的所有点的方案数，其中 \(cntr(S)\) 在 \(S\) 中为 red 的个数，\(cntb(S)\) 为在 \(S\) 中 blue 的个数。
不难发现对于某一集合 \(S\) 而言，只有在 \(cntr(S) = cntb(S)\) 时才能连成恰好 \(1\) 个连通块，对于答案才有贡献。因此最终答案为：
\[ans = \sum_S \frac{f_S \times cntr(\overline{S})!}{m!}\]
且容易观察到 \(g_S = cntr(S)!\)
再想一下 \(f_S\) 和 \(g_S\) 的关系，如何求得 \(f_S\) 呢？枚举 \(S\) 的子集 \(T\)，以 \(f_T\) 加权和求得 \(g_S\)，即恰好用 \(T\) 这个集合构成 \(1\) 个连通块，而剩下的随意排布，方案数即为排列数。（下式是个错误式子）
\[g_S = \sum_{T \in S} f_T \times cntr(S \setminus T)!\]
上式的问题之处在于，如果 \(T\) 和 \(S \setminus T\) 同时可以构成恰好 \(1\) 个连通块，那么这种方案数就被算了两遍。因此，可以指定最低位的数 \(a\)，钦定它在集合 \(T\) 中，再推导一下，有：
\[f_S = g_S – \sum_{T \subset S, a \in T} f_T \times cntr(S \setminus T)!\]
这个题就做完了，最后我们证明一下为什么指定最低位的数 \(a\) 转移能不重不漏，将下列四种情况代入回上面式子有：
- 当 \(f_T=0, f_{S\setminus T}=0\)时，无影响
- 当 \(f_T \not =0, f_{S\setminus T}=0\)时，无影响，且这种情况不可能出现
- 当 \(f_T=0, f_{S\setminus T} \not =0\)时，这种情况不可能出现
- 当 \(f_T \not =0, f_{S\setminus T} \not =0\)时，无影响
唯一能影响到答案的情况 3 在当前 \(f_S \not = 0\) 的情况下不可能出现，因此成立。
应用这种指定最低位的数 \(a\) 的方法（泛化一下是任意指定某个数的方法）应当满足如下几个要素：
- 求方案数（也许求别的也可以应用）
- 对于某个集合 \(S\)，将其分割为两个集合 \(T\) 和 \(S\setminus T\) 时，满足都同 \(0\) 或都不同 \(0\)，形式化地为以下两个条件中的一个：
- \(f_T=0且f_{S\setminus T}=0\)
- \(f_T \not =0且f_{S\setminus T} \not =0\)
#includeusing namespace std;typedef long long ll;typedef double db;typedef long double ld;#define IL inline#define fi first#define se second#define mk make_pair#define pb push_back#define SZ(x) (int)(x).size()#define ALL(x) (x).begin(), (x).end()#define dbg1(x) cout << #x << " = " << x << ", "#define dbg2(x) cout << #x << " = " << x << endltemplate void _debug(const char* format, T t) { cerr << format << '=' << t << endl;}template void _debug(const char* format, First first, Rest... rest) { while (*format != ',') cerr << *format++; cerr << '=' << first << ','; _debug(format + 1, rest...);}template ostream& operator<<(ostream& os, const vector& V) { os << "[ "; for (const auto& vv : V) os << vv << ", "; os << ']'; return os;}#ifdef LOCAL #define dbg(...) _debug(#__VA_ARGS__, __VA_ARGS__)#else #define dbg(...) #endiftemplate IL void read(Tp &x) { x=0; int f=1; char ch=getchar(); while(!isdigit(ch)) {if(ch == '-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} x *= f;}template IL void read(First &first, Rest&... rest) { read(first); read(rest...);}int buf[42];template IL void write(Tp x) { int p = 0; if(x < 0) { putchar('-'); x=-x;} if(x == 0) { putchar('0'); return;} while(x) { buf[++p] = x % 10; x /= 10; } for(int i=p;i;i--) putchar('0' + buf[i]);}template IL void write(const First& first, const Rest&... rest) { write(first); putchar(32); write(rest...);}#include using mint = atcoder::modint998244353;void solve() { int n, m; read(n, m); vector cntr(1 << n), cntb(1 << n); for (int i = 0; i < m; i++) { int r; read(r); r--; cntr[1 << r]++; } for (int i = 0; i < m; i++) { int b; read(b); b--; cntb[1 << b]++; } for (int S = 2; S < (1 << n); S++) { if (__builtin_popcount(S) < 2) continue; for (int i = 0; i > i & 1) { cntr[S] += cntr[1 << i]; cntb[S] += cntb[1 << i]; } } vector f(1 << n), g(1 << n); vector J(m + 1); J[0] = 1; for (int i = 1; i <= m; i++) J[i] = J[i-1] * i; mint ans = 0; for (int S = 1; S < (1 < S - T; T = (T - 1) & S) { f[S] -= f[T] * g[S - T]; } ans += f[S] * J[m - cntr[S]]; } ans /= J[m]; write(ans.val()); putchar(10);}int main() {#ifdef LOCAL freopen("test.in", "r", stdin); // freopen("test.out", "w", stdout);#endif int T = 1; // read(T); while(T--) solve(); return 0;}