Description：

给定一正整数 $n$ ，对 $n$ 个点有标号的有向无环图(可以不连通)进行计数，输出答案 $mod 998244353$ 的结果。

$1\leqslant n\leqslant 10^5$

Solution：

考虑 $DP$ ，从入度为 $0$ 的点入手，设 $f(i,j)$ 表示 $i$ 个点中有 $j$ 个入度为 $0$ 的点，转移时枚举删掉这 $j$ 个点后的入度为 $0$ 的点的个数 $k$ ： $$ f[i][j]=C_i^j\sum_{k=1}^{i-j}(2^j-1)^k2^{j(i-j-k)}f[i-j][k] $$ 这样得到了一个 $O(n^3)$ 的 $DP$ ，考虑优化它，发现状态定义太严格，不好转移。

考虑求解 $n$ 个点的方案数，然后再容斥： $$ f[n]=\sum_{k=1}^n(-1)^{k+1}C_n^k2^{k(n-k)}f[n-k] $$ 大概就是保证至少 $k$ 个点入度为 $1$ ，选出这些点有 $C_n^k$ 种方案，往后的连边情况是 $2^{k(n-k)}$ ，剩下的方案数为 $f[n-k]$ 。

这样我们就得到了一个 $O(n^2)$ 的 $DP$ ，发现这个和卷积的形式很相似，于是再化一下： $$ f[n]=\sum_{k=1}^n\bigl((-1)^{k+1}C^k_n\bigr)\times f[n-k]\times 2^{k(n-k)} $$ 于是我们现在唯一的问题就是 $2^{k(n-k)}$ 怎么处理，由于 $2^{(n-k)^2}=2^{n^2-2nk+k^2}$ ，所以： $$ 2^{k(n-k)}=2^{\frac{n^2-k^2-(n-k)^2}2}=\sqrt2^{n^2-k^2-(n-k)^2} $$

$$ f[n]=\Biggl(\sum_{k=1}^n\Bigl((-1)^{k+1}(k!)^{-1}(\sqrt2)^{-k^2}\Bigr)\times \Bigl(f[n-k]((n-k)!)^{-1}(\sqrt2^{-(n-k)^2})\Bigr)\Biggr)\times n!\sqrt2^{n^2} $$

注意由于 $2$ 与 $\varphi(P)=P-1$ 不互质，所以没有逆元，要求二次剩余，但是不用 $cipolla$ ，只要暴枚每个判断就行了。

这个式子怎么求？可以先移项： $$ \frac{f[n]}{n!\sqrt2^{n^2}}=\Biggl(\sum_{k=1}^n\Bigl((-1)^{k+1}(k!)^{-1}(\sqrt2)^{-k^2}\Bigr)\times \Bigl(\frac{f[n-k]}{(n-k)!\sqrt2^{(n-k)^2}}\Bigr)\Biggr) $$ 这样式子就好看了许多，于是设： $$ \begin{align} F[i]&=\frac{f[i]}{i!\sqrt2^{i^2}}\\ G[i]&=(-1)^{i+1}(i!)^{-1}(\sqrt2)^{-i^2}\\ \end{align} $$ 这样就有： $$ F[i]=\sum_{k=1}^iG[k]\times F[i-k] $$ 这样就是一个标准的分治 $FFT$ 的形式，可以用多项式求逆解决。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 300010

#define P 998244353

#define REM2 116195171

typedef long long ll;

ll F[MAXN],G[MAXN];

ll fac[MAXN],inv[MAXN];

ll power(ll a,ll b)

{

	ll res = 1;

	while(b > 0)

	{

		if(b & 1)res = res * a % P;

		a = a * a % P;

		b = b >> 1;

	}

	return res;

}

ll C(ll n,ll m)

{

	return fac[n] * inv[m] % P * inv[n - m] % P;

}

ll inver(ll k){return power(k,P - 2);}

ll ww[MAXN << 1],*g = ww + MAXN;

int rev[MAXN];

ll c[MAXN];

void NTT(ll f[],int l,int type)

{

	for(int i = 0;i < l;++i)

	{

		if(i < rev[i])swap(f[i],f[rev[i]]);

	}

	for(int i = 2;i <= l;i = i << 1)

	{

		ll wn = g[type * l / i];

		for(int j = 0;j < l;j += i)

		{

			ll w = 1;

			for(int k = j;k < j + i / 2;++k)

			{

				ll u = f[k],t = w * f[k + i / 2] % P;

				f[k] = (u + t) % P;

				f[k + i / 2] = (u - t + P) % P;

				w = w * wn % P;

			}

		}

	}

	if(type == -1)

	{

		ll invl = power(l,P - 2);

		for(int i = 0;i < l;++i)f[i] = f[i] * invl % P;

	}

	return;

}

void calc_inv(int deg,ll a[],ll b[])

{

	if(deg == 1)

	{

		b[0] = power(a[0],P - 2);

		return;

	}

	calc_inv((deg + 1) >> 1,a,b);

	int l = 0,len = 1;

	for(;len < (deg << 1);len = len << 1)++l;

	for(int i = 0;i < len;++i)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));

	g[0] = g[-len] = 1;g[1] = g[1 - len] = power(3,(P - 1) / len);

	for(int i = 2;i < len;++i)g[i] = g[i - len] = g[i - 1] * g[1] % P;

	for(int i = 0;i < deg;++i)c[i] = a[i];

	for(int i = deg;i < len;++i)c[i] = 0;

	NTT(c,len,1);NTT(b,len,1);

	for(int i = 0;i < len;++i)b[i] = (2 * b[i] % P - c[i] * b[i] % P * b[i] % P + P) % P;

	NTT(b,len,-1);

	for(int i = deg;i < len;++i)b[i] = 0;

	return;

}

int main()

{

	freopen("dag_count.in","r",stdin);

	freopen("dag_count.out","w",stdout);

	scanf("%d",&n);

	fac[0] = 1;

	for(int i = 1;i <= n;++i)fac[i] = fac[i - 1] * i % P;

	inv[n] = power(fac[n],P - 2);

	for(int i = n - 1;i >= 0;--i)inv[i] = inv[i + 1] * (i + 1) % P;

	for(int i = 1;i <= n;++i)

	{

		G[i] = (((i & 1) ? 1 : -1) * inv[i] * power(inver(REM2),1ll * i * i) % P + P) % P;

	}

	for(int i = 1;i <= n;++i)G[i] = (P - G[i]) % P;

	G[0] = 1;

	calc_inv(n + 1,G,F);

	F[n] = F[n] * fac[n] % P * power(REM2,1ll * n * n) % P;

	cout << F[n] << endl;

	fclose(stdin);

	fclose(stdout);

	return 0;

}