「AGC021F」Trinity


题目

点这里看题目。

分析

显然这是一道 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;
}

原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/tech/pnotes/270796.html

(0)
上一篇 2022年6月30日 11:16
下一篇 2022年6月30日 11:17

相关推荐

发表回复

登录后才能评论