为了更好的阅读体验,请点击这里
题目链接: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\)
#include<bits/stdc++.h>
using 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 << endl
template <typename T>
void _debug(const char* format, T t) {
cerr << format << '=' << t << endl;
}
template <class First, class... Rest>
void _debug(const char* format, First first, Rest... rest) {
while (*format != ',') cerr << *format++;
cerr << '=' << first << ',';
_debug(format + 1, rest...);
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& V) {
os << "[ ";
for (const auto& vv : V) os << vv << ", ";
os << ']';
return os;
}
#ifdef LOCAL
#define dbg(...) _debug(#__VA_ARGS__, __VA_ARGS__)
#else
#define dbg(...)
#endif
template<typename Tp> 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<typename First, typename... Rest> IL void read(First &first, Rest&... rest) {
read(first); read(rest...);
}
int buf[42];
template<typename Tp> 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<typename First, typename... Rest> IL void write(const First& first, const Rest&... rest) {
write(first); putchar(32); write(rest...);
}
#include <atcoder/modint.hpp>
using mint = atcoder::modint998244353;
void solve() {
int n, m; read(n, m);
vector<int> 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 < n; i++) if (S >> i & 1) {
cntr[S] += cntr[1 << i];
cntb[S] += cntb[1 << i];
}
}
vector<mint> f(1 << n), g(1 << n);
vector<mint> 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 << n); S++) {
if (cntr[S] != cntb[S]) continue;
f[S] = g[S] = J[cntr[S]];
for (int T = (S - 1) & S; T > 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;
}
- 题解 Beginner Electric Atcoder Contest题解beginner electric atcoder 题解beginner atcoder contest contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest abcde beginner atcoder contest 295 beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 315