题目

点这里看题目。

分析

显然这是一道 DP 题目。

显然，由于 /(B,C/) 都是关于列，只有 /(A/) 是关于行的，我们应该逐列做 DP。

状态有一点小技巧，我们可以设 /(f_{i,j}/) 表示前 /(i/) 列，其中有 /(j/) 行出现了第一个黑格子，且这 /(j/) 行的相对顺序已经确定的方案数。

Note.

从顺序的角度来看，在 DP 的一维状态中维护集合，一般来说我们有三种策略：

1. 知道元素的绝对位置，也就是知道了元素具体是多少。

2. 知道元素的相对位置，也就是还不知道元素具体是多少，但是知道大小偏序。

3. 啥也不知道，就只知道元素个数。

三种策略所携带的信息量和各自转移难度都是随标号递减的。具体使用还需要依情况而定。

一般来说，第一种策略可能意味着需要“状压”集合，不过也不是必要的，也有可能只是需要定标号而已。

在这里使用第一种策略不够方便，主要是因为转移的时候，知道了绝对位置会导致之后加入新元素时，新元素不方便处理和旧元素的大小关系。

接下来考虑转移：

• 不染色，方案为 /(f_{i-1,j}/)。

• 没有新的行出现了第一个黑格子。我们只需要在已有的行里面选一或两个出来染就好了，方案数为 /(/binom{j+1}{2}f_{i-1,j}/)。

• 有新的行出现了第一个黑格子。如果从状态 /(f_{i-1,k}/) 转移过来，转移系数通过讨论之后可以得到为 /(/binom{j+2}{k}/)，这一部分贡献为：

  /[/sum_{k<j}/binom{j+2}{k}f_{i-1,k}
  /]

  Note.

  一个好玩的组合意义是，我们可以假想原有的行为黑色，新来的行为白色。不过我们要对 /(k/) 个黑行与 /(j-k+2/) 个白行做归并。真正要加入的白行其实是掐头去尾中间的 /(j-k/) 个白行。前后的 /(2/) 个用于定位 /(B,C/)。

  这样进行了归并之后，第一个白行的前一个和最后一个白行的后一个就对应了 /(B,C/) 的取值（如果没有了，就认为是 /(B,C/) 取到了白行的首或尾）。

转移式子是：

/[f_{i,j}=f_{i-1,j}+/binom{j+1}{2}f_{i-1,j}+/sum_{k<j}/binom{j+2}{k}f_{i-1,k}
/]

做卷积即可得到 /(O(nm/log n)/) 的算法。

然而这还不够。我们考虑将转移改写成生成函数的形式。设 /(F_{i}(x)=/sum_{j/ge 0}f_{i,j}/frac{x^j}{j!}/)，则我们可以通过转移式子建立微分方程：

/[F_i=e^xF_{i-1}+(2e^x-x-2)F’_{i-1}+(e^x-x-1)F”_{i-1}
/]

Note.

怎么改写？勉强摸索出了一个有点流程的方法。

以 /(f_{i,j}=/binom{j+1}{2}f_{i-1,j}/) 为例，我们可以调整成需要的单项形式：

/[f_{i,j}/frac{x^j}{(j+1)!}=f_{i-1,j}/frac{x^j}{(j-1)!}/frac{1}{2!}
/]

尝试通过生成函数的变形得到左右的式子，比如这里 /(f_{i,j}/frac{x^j}{(j+1)!}=x^{-1}/int f_{i,j}/frac{x^j}{j!}/text dx/)。由于运算性质我们可以拓展到对于生成函数本身的方程：

/[x^{-1}/int F_i /text dx=/frac{x}{2!}F’_{i-1}
/]

解出来就可以得到需要的东西了。

这是不是有点像抄的《具体数学》的啊

关键在于，观察这个形式，我们发现 /(F_{i}/) 一定可以被表示为 /(/sum_{p/ge 0}/sum_{q/ge 0}g_{i,p,q}x^pe^{qx}/)。进而，我们只需要维护 /(g/)，而这在上面的方程的背景之下是非常容易的，单次只需要 /(O(m^2)/)。

最终，我们可以得到 /(O(m^3+n)/) 的算法。

代码

#include <cstdio>

#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 MAXM = 205, MAXN = 8e3 + 5;

template<typename _T>
void read( _T &x ) {
	x = 0; char s = getchar(); int f = 1;
	while( ! ( '0' <= s && s <= '9' ) ) { f = 1; if( s == '-' ) f = -1; s = getchar(); }
	while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar(); }
	x *= f;
}

template<typename _T>
void write( _T x ) {
	if( x < 0 ) putchar( '-' ), x = -x;
	if( 9 < x ) write( x / 10 );
	putchar( x % 10 + '0' );
}

int fac[MAXN], ifac[MAXN];

int g[MAXM][MAXM], g_[MAXM][MAXM], g__[MAXM][MAXM], tmp[MAXM][MAXM];

int N, M;

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 Down( const int &x, const int &r ) { return x < r ? 0 : Mul( fac[x], ifac[x - r] ); }

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

inline void Init( const int &n ) {
	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 );
}

int main() {
	g[0][0] = 1;
	read( N ), read( M ), Init( N );
	rep( i, 1, M ) {
		rep( j, 0, M ) rep( k, 0, M )
			g_[j][k] = Add( Mul( j + 1, g[j + 1][k] ), Mul( k, g[j][k] ) );
		rep( j, 0, M ) rep( k, 0, M )
			g__[j][k] = Add( Mul( j + 1, g_[j + 1][k] ), Mul( k, g_[j][k] ) );
		rep( j, 0, M ) rep( k, 0, M ) {
			AddEq( tmp[j][k + 1], g[j][k] );
			AddEq( tmp[j][k + 1], Mul( 2, g_[j][k] ) );
			SubEq( tmp[j + 1][k], g_[j][k] );
			SubEq( tmp[j][k], Mul( 2, g_[j][k] ) );
			AddEq( tmp[j][k + 1], g__[j][k] );
			SubEq( tmp[j + 1][k], g__[j][k] );
			SubEq( tmp[j][k], g__[j][k] );
		}
		rep( j, 0, M ) rep( k, 0, M ) g[j][k] = tmp[j][k], tmp[j][k] = 0;
	}
	int ans = 0;
	for( int j = 0 ; j <= M && j <= N ; j ++ )
		rep( k, 0, M ) AddEq( ans, Mul( g[j][k], Mul( Qkpow( k + 1, N - j ), Down( N, j ) ) ) );
	write( ans ), putchar( '/n' );
	return 0;
}