题意
对于一对长度均为 \(M\) 且元素值在 \(\left[1, N\right]\) 之间的序列 \((S, T)\)，定义其为好的当且仅当：
-
存在一个长度为 \(N\) 的 \(01\) 序列 \(X\)，使得其满足如下条件：
- 对于任意 \(i \in \left[1, M\right]\)，有 \(X_{S_i} \neq X_{T_i}\)。
给定 \(N, M\)，求在所有可能的 \(N^{2M}\) 种长度均为 \(M\) 且元素值在 \(\left[1, N\right]\) 之间的序列对 \((A, B)\) 中，有多少对序列是好的。
对 \(998244353\) 取模。
\(1 \le N \le 30, 1 \le M \le 10^9\)。
题解
发现对于所有的 \(i \in \left[1, M\right]\)，可以建边 \((S_i, T_i)\)。其中每一条边均代表着其连接的两个顶点的 \(X\) 值不能相同。由于 \(X_i\) 的取值只有两种，那么一个对序列合法当且仅当其建出的图为二分图。
所以我们可以对 \(N\) 个点，\(M\) 条边的二分图进行计数，设其为 \(a(N, M)\)。由于一条边 \((u, v)\) 可以对应 \((S_i, T_i)\) 或 \((T_i, S_i)\)，所以最终答案即为 \(a(N, M) \times 2^M\)。
发现由 \(N\) 个点组成的二分图最多有 \(\left\lfloor\frac{N}{2}\right\rfloor \times \left\lceil\frac{N}{2}\right\rceil\) 种本质不同的边，设其为 \(L\)。那么我们可以将 \(M\) 条边进行分类，设 \(b(M, k)\) 代表将 \(M\) 条相互区分的边划分为 \(k\) 个相互区分的集合的方案数，\(f(n, k)\) 代表 \(n\) 个点，\(k\) 条本质不同的边的二分图数量，那么有
\[a(N, M) = \sum\limits_{k = 0}^{L} b(M, k) \times f(N, k) \]下面考虑如何求出 \(b(M, k)\) 的值，根据斯特林数的定义，有
\[b(M, k) = {M \brace k} k! \]考虑斯特林数的通项公式
\[{n \brace m} = \sum\limits_{i = 0}^{m} \dfrac{\left(-1\right)^{m - i} i^n}{i! \times (m - i)!} \]将其代入，有
\[\begin{aligned} b(M, k) &= {M \brace k} k! \\ &= \sum\limits_{i = 0}^{k} \dfrac{\left(-1\right)^{k - i} i^M}{i! \times (k - i)!} \times k! \\ &= \sum\limits_{i = 0}^{k} \left(-1\right)^{k - i} \dbinom{k}{i} i^M \end{aligned}\]通过预处理组合数，我们可以在 \(\mathcal{O}(N^4 \log M)\) 的复杂度内计算出 \(b(M, 0), b(M, 1), b(M, 2), \cdots, b(M, L)\) 的值。
下面我们考虑如何求出 \(f(N, k)\) 的值，考虑应用容斥 \(\tt{DP}\)。
设 \(g(n, m)\) 代表将 \(n\) 个点黑白染色后，存在 \(m\) 条本质不同的边使得每个边连接的两个顶点颜色均不同的方案数，通过枚举白色点的数量，我们有
\[g(n, m) = \sum\limits_{i = 0}^{n} \dbinom{n}{i} \dbinom{i \times \left(n - i\right)}{m} \]发现我们不能通过 \(g\) 的值计算出 \(f\) 的值，原因为在 \(g\) 的计算中，每一个联通块都会被重复计算两次（考虑钦定每个联通块编号最小的点的颜色为黑色或白色），而 \(g(n, m)\) 中计算了多少个联通快是不便于计算的，因此我们需要计算出将 \(n\) 个点黑白染色后，存在 \(m\) 条本质不同的边使得每个边连接的两个顶点颜色均不同且使得图联通的方案数，设其为 \(h(n, m)\)。
考虑如何计算其值，我们可以考虑容斥掉 \(g(n, m)\) 中的不合法情况，若存在图使得其不合法，那么其一定存在多于一个联通块，也就是说 \(1\) 号节点所在的联通块大小不为 \(n\)。可以发现，\(1\) 号节点所在的联通块大小等于 \(n\) 与图联通为充要条件。因此我们可以通过枚举 \(1\) 号节点所在联通块的大小来计算不合法情况的方案数，有
\[h(n, m) = g(n, m) - \sum\limits_{i = 1}^{n - 1}\sum\limits_{j = 0}^{m} \dbinom{n - 1}{i - 1}h(i, j)g(n - i, m - j) \]发现对于一个图，因为 \(1\) 号节点的颜色不确定，所以其在 \(h(n, m)\) 的中会被计算两次。
下面考虑如何计算 \(f(n, m)\)，发现若图不联通，我们可以通过枚举 \(1\) 号节点所在联通块的大小完成计算，有
\[f(n,m) = \dfrac{h(n,m)}{2} + \sum\limits_{1 \le i < n}\sum\limits_{0 \le j \le m}\dbinom{n-1}{i-1}\dfrac{h(i, j)}{2}f(n -i, m - j) \]至此我们以 \(\mathcal{O}(N^6)\) 的复杂度完成了 \(f(N, k), k \in \left[0, L\right]\) 的计算。
总复杂度为 \(\mathcal{O}(N^6 + N^4 \log M)\)，可以通过。
Code
#include <bits/stdc++.h>
typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
namespace MODINT {
constexpr valueType MOD = 998244353;
template<typename T1, typename T2, typename T3 = valueType>
void Inc(T1 &a, T2 b, const T3 &mod = MOD) {
a = a + b;
if (a >= mod)
a -= mod;
}
template<typename T1, typename T2, typename T3 = valueType>
void Dec(T1 &a, T2 b, const T3 &mod = MOD) {
a = a - b;
if (a < 0)
a += mod;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 sum(T1 a, T2 b, const T3 &mod = MOD) {
return a + b >= mod ? a + b - mod : a + b;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 sub(T1 a, T2 b, const T3 &mod = MOD) {
return a - b < 0 ? a - b + mod : a - b;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 mul(T1 a, T2 b, const T3 &mod = MOD) {
return (long long) a * b % mod;
}
template<typename T1, typename T2, typename T3 = valueType>
void Mul(T1 &a, T2 b, const T3 &mod = MOD) {
a = (long long) a * b % mod;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 pow(T1 a, T2 b, const T3 &mod = MOD) {
T1 result = 1;
while (b > 0) {
if (b & 1)
Mul(result, a, mod);
Mul(a, a, mod);
b = b >> 1;
}
return result;
}
}// namespace MODINT
using namespace MODINT;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
valueType N, M;
std::cin >> N >> M;
valueType const L = (N / 2) * ((N + 1) / 2), S = L + 100;
ValueMatrix C(S + 1, ValueVector(S + 1, 0));
C[0][0] = 1;
for (valueType i = 1; i <= S; ++i) {
C[i][0] = 1;
for (valueType j = 1; j <= i; ++j)
C[i][j] = sum(C[i - 1][j - 1], C[i - 1][j]);
}
ValueVector divideCount(L + 1, 0);
for (valueType k = 0; k <= L; ++k) {
divideCount[k] = 0;
for (valueType i = 0; i <= k; ++i) {
if ((k - i) & 1)
Dec(divideCount[k], mul(C[k][i], pow(i, M)));
else
Inc(divideCount[k], mul(C[k][i], pow(i, M)));
}
}
ValueMatrix F(N + 1, ValueVector(L + 1, 0)), G(N + 1, ValueVector(L + 1, 0)), H(N + 1, ValueVector(L + 1, 0));
// calc G
for (valueType n = 1; n <= N; ++n)
for (valueType m = 0; m <= L; ++m)
for (valueType i = 0; i <= n; ++i)
Inc(G[n][m], mul(C[n][i], C[i * (n - i)][m]));
// calc H
for (valueType n = 1; n <= N; ++n) {
for (valueType m = 0; m <= L; ++m) {
H[n][m] = G[n][m];
for (valueType i = 1; i < n; ++i)
for (valueType j = 0; j <= m; ++j)
Dec(H[n][m], mul(C[n - 1][i - 1], mul(H[i][j], G[n - i][m - j])));
}
}
constexpr valueType Inv2 = (MOD + 1) / 2;
for (auto &h : H)
for (auto &iter : h)
Mul(iter, Inv2);
// calc F
for (valueType n = 1; n <= N; ++n) {
for (valueType m = 0; m <= L; ++m) {
F[n][m] = H[n][m];
for (valueType i = 1; i < n; ++i)
for (valueType j = 0; j <= m; ++j)
Inc(F[n][m], mul(C[n - 1][i - 1], mul(H[i][j], F[n - i][m - j])));
}
}
valueType ans = 0;
for (valueType i = 0; i <= L; ++i)
Inc(ans, mul(F[N][i], divideCount[i]));
Mul(ans, pow(2, M));
std::cout << ans << std::endl;
return 0;
}