代码
点这里看题目。
有一个 \(n\) 个点的无向有标号完全图，你需要给每一条边染上红色或者蓝色。
对于一个点集 \(S\)（\(|S|\ge 2\)），如果仅保留红边时 \(S\) 中的点是连通的，则称 \(S\) 是 R-连通的；相应地可以定义 B-连通。
现在，你需要计算满足以下条件的染色方案数：
- 有至少一条染成红色的边，有至少一条染成蓝色的边。
- 对于任意一个点集 \(S\)（\(|S|\ge 2\)），\(S\) 必须是 R-连通或者 B-连通，但不能同时是 R-连通和 B-连通。
答案对 \(998244353\) 取模。
所有数据满足 \(1\le n\le 5\times 10^4\)。
分析
设 \(G=(V,E),E=E_B\cup E_R\)，其中 \(E_B,E_R\) 为蓝色边和红色边的边集。则考察 \(V\) 的连通性可以知道，\(G_B=(V,E_B)\) 和 \(G_R=(V,E_R)\) 中恰好有一个是不连通的。不妨设 \(G_R\) 连通，而 \(G_B\) 不连通，那么 \(V\) 被 \(E_B\) 划分为了若干个连通块，且因为 \(E_R=\complement_EE_B\)，\(G_B\) 的确是连通的。
考察连通块的子结构，我们发现在每个连通块内，诱导子图的结构和原图图完全相同，只不过颜色相反。于是，这里的“染色”就有一种“递归”的结构。
所以，设 \(f_n\) 为 \(|V|=n\) 时可能的 \(E_B\) 的数量（包括 \(E_B=\varnothing\)），设 \(F(x)\) 为 \(\{f_n\}\) 的 EGF，则可以列一个方程：
\[F=\exp F-F-1+x \]Note.
写方程的时候需要注意边界的修正。
这里的“递归”结构仅仅在 \(n\ge 2\) 时成立，所以需要对于 \(f_0,f_1\) 进行修正。另一方面，需要修正的项事先是已知的，所以修正前的错误值可以被直接算出来。
之后有两种计算方式。其一是写成 \(\exp F-2F+x-1=0\)，然后牛迭解方程。另一种是变成 \(-\exp F+2F+1=x\)，然后用拉格朗日反演算单项。后者在此要简单一些。
复杂度为 \(O(n\log n)\) 或 \(O(n\log^2n)\)。
代码
用的是拉格朗日反演。代码里写的是 \(O(n\log^2n)\) 分治算多项式幂。
#include <cstdio>
#include <vector>
#include <algorithm>
#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )
const int mod = 998244353;
const int MAXN = ( 1 << 17 ) + 5;
template<typename _T>
inline void Read( _T &x ) {
x = 0; char s = getchar(); bool f = false;
while( ! ( '0' <= s && s <= '9' ) ) { f = s == '-', s = getchar(); }
while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar(); }
if( f ) x = -x;
}
template<typename _T>
inline void Write( _T x ) {
if( x < 0 ) putchar( '-' ), x = -x;
if( 9 < x ) Write( x / 10 );
putchar( x % 10 + '0' );
}
int F[MAXN], H[MAXN], P[MAXN], Q[MAXN];
int fac[MAXN], ifac[MAXN];
int N;
inline int Qkpow( int, int );
inline int Inv( const int &a ) { return Qkpow( a, mod - 2 ); }
inline int Mul( int x, const int &v ) { return 1ll * x * v % mod; }
inline int Sub( int x, const int &v ) { return ( x -= v ) < 0 ? x + mod : x; }
inline int Add( int x, const int &v ) { return ( x += v ) >= mod ? x - mod : x; }
inline int& MulEq( int &x, const int &v ) { return x = 1ll * x * v % mod; }
inline int& SubEq( int &x, const int &v ) { return ( x -= v ) < 0 ? ( x += mod ) : x; }
inline int& AddEq( int &x, const int &v ) { return ( x += v ) >= mod ? ( x -= mod ) : x; }
inline int C( int n, int m ) { return n < m ? 0 : Mul( fac[n], Mul( ifac[m], ifac[n - m] ) ); }
inline int Qkpow( int base, int indx ) {
int ret = 1;
while( indx ) {
if( indx & 1 ) MulEq( ret, base );
MulEq( base, base ), indx >>= 1;
}
return ret;
}
namespace Basics {
const int L = 17, g = 3, phi = mod - 1;
int w[MAXN];
inline void NTTInit( const int &n = 1 << L ) {
w[0] = 1, w[1] = Qkpow( g, phi >> L );
rep( i, 2, n - 1 ) w[i] = Mul( w[i - 1], w[1] );
}
inline void DIF( int *coe, const int &n ) {
int *wp, p, e, o;
for( int s = n >> 1 ; s ; s >>= 1 )
for( int i = 0 ; i < n ; i += s << 1 ) {
p = ( 1 << L ) / ( s << 1 ), wp = w;
for( int j = 0 ; j < s ; j ++, wp += p ) {
e = coe[i + j], o = coe[i + j + s];
coe[i + j] = Add( e, o );
coe[i + j + s] = Mul( *wp, Sub( e, o ) );
}
}
}
inline void DIT( int *coe, const int &n ) {
int *wp, p, k;
for( int s = 1 ; s < n ; s <<= 1 )
for( int i = 0 ; i < n ; i += s << 1 ) {
p = ( 1 << L ) / ( s << 1 ), wp = w;
for( int j = 0 ; j < s ; j ++, wp += p )
k = Mul( *wp, coe[i + j + s] ),
coe[i + j + s] = Sub( coe[i + j], k ),
coe[i + j] = Add( coe[i + j], k );
}
std :: reverse( coe + 1, coe + n );
int inv = Inv( n ); rep( i, 0, n - 1 ) MulEq( coe[i], inv );
}
}
inline void Init( const int &n ) {
Basics :: NTTInit();
fac[0] = 1; rep( i, 1, n ) fac[i] = Mul( fac[i - 1], i );
ifac[n] = Inv( fac[n] ); per( i, n - 1, 0 ) ifac[i] = Mul( ifac[i + 1], i + 1 );
}
void Divide( const int &l, const int &r ) {
if( l == r ) {
if( ! l ) H[0] = Qkpow( F[0], mod - 1 - N );
else MulEq( H[l], Inv( mod - l ) );
return ;
}
int mid = ( l + r ) >> 1, L;
Divide( l, mid );
for( L = 1 ; L <= r - l ; L <<= 1 );
rep( i, 0, L - 1 ) P[i] = Q[i] = 0;
rep( i, l, mid ) P[i - l] = H[i];
rep( i, 1, r - l ) Q[i] = Mul( F[i], i );
Basics :: DIF( P, L );
Basics :: DIF( Q, L );
rep( i, 0, L - 1 ) MulEq( P[i], Q[i] );
Basics :: DIT( P, L );
rep( i, mid + 1, r ) AddEq( H[i], Mul( N, P[i - l] ) );
rep( i, 0, L - 1 ) P[i] = Q[i] = 0;
rep( i, l, mid ) P[i - l] = Mul( H[i], i );
rep( i, 1, r - l ) Q[i] = F[i];
Basics :: DIF( P, L );
Basics :: DIF( Q, L );
rep( i, 0, L - 1 ) MulEq( P[i], Q[i] );
Basics :: DIT( P, L );
rep( i, mid + 1, r ) AddEq( H[i], P[i - l] );
Divide( mid + 1, r );
}
int main() {
Read( N ), Init( N );
rep( i, 1, N ) F[i - 1] = mod - ifac[i];
AddEq( F[0], 2 );
Divide( 0, N - 1 );
Write( Mul( 2, Sub( Mul( fac[N - 1], H[N - 1] ), 1 ) ) ), putchar( '\n' );
return 0;
}