洛谷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;
}