题目
点这里看题目。
分析
显然这是一道 DP 题目。
显然,由于 /(B,C/) 都是关于列,只有 /(A/) 是关于行的,我们应该逐列做 DP。
状态有一点小技巧,我们可以设 /(f_{i,j}/) 表示前 /(i/) 列,其中有 /(j/) 行出现了第一个黑格子,且这 /(j/) 行的相对顺序已经确定的方案数。
Note.
从顺序的角度来看,在 DP 的一维状态中维护集合,一般来说我们有三种策略:
知道元素的绝对位置,也就是知道了元素具体是多少。
知道元素的相对位置,也就是还不知道元素具体是多少,但是知道大小偏序。
啥也不知道,就只知道元素个数。
三种策略所携带的信息量和各自转移难度都是随标号递减的。具体使用还需要依情况而定。
一般来说,第一种策略可能意味着需要“状压”集合,不过也不是必要的,也有可能只是需要定标号而已。
在这里使用第一种策略不够方便,主要是因为转移的时候,知道了绝对位置会导致之后加入新元素时,新元素不方便处理和旧元素的大小关系。
接下来考虑转移:
-
不染色,方案为 /(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