一、题目：
二、思路：
经典的图计数问题。在这里说明一下，由于笔者不会多项式全家桶，所以代码的时间复杂度是 \(O(n^2)\) 的。
首先设 \(g_i\) 表示区分左部和右部、图不一定连通、含有 \(i\) 个点的方案数。则有 \(g_i=\sum\limits_{j=0}^i\dbinom{i}{j}3^{j(i-j)}\)。
注意，\(\dfrac{g_n}{2}\) 不是最终的答案！细想一下，$g_n $ 表示将 \(n\) 个点分入可区分的两个集合，那么 \(g_n/2\) 表示将 \(n\) 个点分入不可区分的两个集合。比如说 \(\dfrac{g_2}{2}=4\)，分别代表了这四种情况：
但是我们发现情况 1 和情况 2 代表了相同的图。
设 \(f_i\) 表示不区分左部和右部、保证图是连通的、包含 \(i\) 个点的方案数。则有
\[f_i=\dfrac{g_i}{2}-\sum\limits_{j=1}^{i-1}\dbinom{i-1}{j-1}\times f_j\times g_{i-j}
\]
用总方案数减去不连通的方案数。如何算出不连通的方案数呢？考虑枚举 1 号点所在连通块的大小 \(j\)。我们发现，“不区分左部和右部”\(\Leftrightarrow\)“规定 1 号点所在‘部’为左部”。所以剩下的 \(i-j\) 个点仍要区分左右部。
最后设 \(h_i\) 为包含 \(i\) 个点的黑白图的数量。则有
\[h_i=\sum\limits_{j=1}^i \dbinom{i-1}{j-1}\times f_{j}\times h_{i-j}
\]
三、代码；
// 64分的代码
#include <iostream>
#include <cstdio>
#include <ctime>
#include <cstring>
using namespace std;
#define FILEIN(s) freopen(s, "r", stdin)
#define FILEOUT(s) freopen(s, "w", stdout)
#define mem(s, v) memset(s, v, sizeof s)
inline int read(void) {
int x = 0, f = 1; char ch = getchar();
while (ch < ‘0‘ || ch > ‘9‘) { if (ch == ‘-‘) f = -1; ch = getchar(); }
while (ch >= ‘0‘ && ch <= ‘9‘) { x = x * 10 + ch - ‘0‘; ch = getchar(); }
return f * x;
}
const int MOD = 998244353, MAXN = 7000;
int factor[MAXN], facinv[MAXN], div2;
int g[MAXN], f[MAXN], h[MAXN], N;
inline int power(int a, int b) {
int res = 1;
for (; b; b >>= 1) {
if (b & 1) res = 1LL * res * a % MOD;
a = 1LL * a * a % MOD;
}
return res;
}
inline int C(int n, int m) {
return 1LL * factor[n] * facinv[m] % MOD * facinv[n - m] % MOD;
}
inline void Add(int &a, int b) {
a += b;
if (a >= MOD) a -= MOD;
}
void prework(void) {
factor[0] = 1;
for (int i = 1; i <= N; ++ i)
factor[i] = 1LL * factor[i - 1] * i % MOD,
facinv[N] = power(factor[N], MOD - 2);
for (int i = N - 1; i >= 0; -- i) facinv[i] = 1LL * facinv[i + 1] * (i + 1) % MOD;
div2 = facinv[2];
h[0] = 1;
for (int i = 1; i <= N; ++ i) {
g[i] = 2;
for (int j = 1; j <= i - 1; ++ j) {
Add(g[i], 1LL * C(i, j) * power(3, j * (i - j)) % MOD);
Add(f[i], 1LL * f[j] * g[i - j] % MOD * C(i - 1, j - 1) % MOD);
Add(h[i], 1LL * f[j] * C(i - 1, j - 1) % MOD * h[i - j] % MOD);
}
f[i] = (1LL * g[i] * div2 % MOD - f[i] + MOD) % MOD;
Add(h[i], f[i]);
}
}
int main() {
FILEIN("graph.in"); FILEOUT("graph.out");
N = read();
prework();
while (N --) printf("%d\n", h[read()]);
return 0;
}