洛谷P3673 小清新计数题题解

题意：

小 A 正在电脑上玩一个叫做 Truth or Lie 的游戏。

游戏开始时电脑会给出 $n$ 句话，每句话形如「第 $x$ 句话为真」或「第 $x$ 句话为假」，

其中 $x$ 是一个 $1$ 到 $n$ 的整数，你只要选择 Good 或者 Bad，Good 表示可以决定每句话的真假使每句话的内容都成立，Bad 反之。

作为一个菜鸡，小 A 只会不停地点 Good，靠脸过关。

在无数次失败后，非洲人小 A 发现游戏每关中，每句话包含的是「真」还是「假」是固定的，但是每句话中的 $x$ 是在 $1$ 到 $n$ 均匀随机的。

现在小 A 告诉了你某一关每句话的真假，用一个 $01$ 序列表示。第 $i$ 位为 $0$ 表示第 $i$ 句话包含「假」，否则表示包含「真」。现在他想要知道使得点击 Good 正确的方案数。

由于方案数可能比较大，你需要输出方案数对 $998244353$ 取模的结果。

输入格式

一行一个 $01$ 序列，它的长度即为 $n$。

输出格式

输出方案数对 $998244353$ 取模的结果。

数据范围：

对于$100\%$ 的数据，$1 \leq n \leq 50$。

省流：求多少种没有矛盾的方案满足真话有 $n_1$ 个且假话有 $n_0$ 个，其中 $n_{1/0}$ 等于给定 $01$ 序列中 $1/0$ 的数量。

注意到

若第 $x$ 句话说 $y$ 是真的，那么 $x$ 为真当且仅当 $y$ 为真；反之 $x$ 为假当且仅当 $y$ 为假。
若第 $x$ 句话说 $y$ 是假的，那么 $x$ 为真当且仅当 $y$ 为假；反之 $x$ 为假当且仅当 $y$ 为真。

如果我们将 $x$ 和 $y$ 连边，边的颜色为白/黑，白的表示真假相同，黑表示真假相对（即上面两种情况）

又因为一共有 $n$ 条边，那么所有话不出现矛盾当且仅当这棵基环树的环上有偶数条黑边。

那么问题变成了如何计算有 $i$ 条白边和 $j$ 条黑边（$j$ 是偶数）的有标号基环树的个数了。

设环上有 $n=a+b$ 个点，其中 $a,b$ 分别为白/黑的边数，记 $m = i + j - a - b$ 。

如果把环看作一个点（称为环点），将它的编号定为 $m+1$ 。

那么方案数相当于 $m + 1$ 个点的无根生成树的个数，这可以用 prüfer 序列来求解。

这 $m + 1$ 个点的 prüfer 序列长 $m-1$ ，每个位置有 $n + m$ 种情况（环点贡献 $n$ 个情况），

又因为剩下的两个点中一个是环点，所以还要乘上 $n$ 表示另一个点连环点的方案

然后环上的 $n$ 个点自己还能排列，共有 $(n-1)!$ 种情况，就是一个圆排列。

那么当 $i,j,a,b$ 均固定时，方案数为

$\binom{i}{a}\binom{j}{b}(n-1)!\,n(n + m)^{m-1}$

现在设 $f(i,j)$ 为 $i$ 条白边和 $j$ 条黑边（$j$ 是偶数）的有标号基环树的个数，那么

$f(i,j) = \sum_{a + b < i + j\, \land\, b \text{ is even}} \binom{i}{a}\binom{j}{b}(a + b)! (i + j)^{i + j - a - b-1} + [j\text{ is even}]\times(i + j - 1)$

最后面那个是考虑只有一个环的情况。

方便起见，我们设 $g(n,m)=n!(n+m)^{m-1}$ ，这个可以预处理出来，那么式子变成了

$f(i,j) = \sum_{a + b \le i + j\, \land\, b \text{ is even}} \binom{i}{a}\binom{j}{b}(a + b)!\ g(a + b,\, i + j - a - b)$

由于题目可能出现基环森林，所以我们得再统计。

设 $\mathrm{Ans}(i,j)$ 为 $i$ 条白边和 $j$ 条黑边（$j$ 为偶数）的基环树森林的方案数。边界 $\mathrm{Ans}(0,0)=1$

考虑转移。显然我们要从 $i,j$ 中分别抽出 $a,b$ 条边来做基环树。

不过这样会重复计算一些情况，因此我们每次需要钦定基环树的根，那么

$\mathrm{Ans}(0,j) = \sum_{1 \le b \le j}\mathrm{Ans}(0,j-b)\binom{j-1}{b-1}f(0,b) \\[6pt]\mathrm{Ans}(i,j) =\sum_{1 \le a \le i}\sum_{0 \le b \le j}\mathrm{Ans}(i - a,j - b) \binom{i-1}{a-1}\binom{j}{b}f(a,b)$

时间复杂度 $\mathcal{O}(n^4)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 998244353;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define rep2(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i += 2)
void add(int &x, int y) { (x += y) >= mod ? x -= mod : 0; }
#define N ((int)(55))

char s[N];
int n, zero, one, fac[N], C[N][N], f[N][N], g[N][N], dp[N][N];
int qpow(int a, int b)
{
    int r = 1;
    for(a %= mod; b > 0; b >>= 1, a = a * a % mod)
        if(b & 1) r = r * a % mod;
    return r;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> (s + 1); n = strlen(s + 1);
    rep(i, 1, n) if(s[i] == '0') ++zero; else ++one;
    fac[0] = 1; rep(i, 1, n) fac[i] = fac[i - 1] * i % mod;
    rep(i, 0, n) C[i][0] = 1;
    rep(i, 1, n) rep(j, 1, n) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
    rep(i, 1, n) rep(j, 0, n - i) g[i][j] = fac[i - 1] * (j ? i : 1) % mod * qpow(i + j, j - 1) % mod;
    rep(i, 0, one) rep(j, 0, zero) rep(a, 0, i) rep2(b, 0, j)
        if(a || b) add(f[i][j],  C[i][a] * C[j][b] % mod * g[a + b][i + j - a - b] % mod);
    dp[0][0] = 1;
    rep(j, 1, zero) rep(b, 1, j) add(dp[0][j], dp[0][j - b] * C[j - 1][b - 1] % mod * f[0][b] % mod);
    rep(i, 1, one) rep(j, 0, zero) rep(a, 1, i) rep(b, 0, j)
        add(dp[i][j], dp[i - a][j - b] * C[i - 1][a - 1] % mod * C[j][b] % mod * f[a][b] % mod);
    cout << dp[one][zero] << '\n';
    return 0;
}