「Gym102978A」Ascending Matrix

题目

点这里看题目。

分析

非常巧妙的一道题目。

首先，我们可以思考如果没有 (a_{R,C}=V) 的限制，问题应该如果求解。一种巧妙的思考方式是，我们可以对于 (iin [1,K)) 勾勒出 (le i) 的元素和 (>i) 的元素之间的分界线。这样的话，如果我们从 0 开始给行列的格点标号，那么每一条分界线一定是从 ((n,0)) 到 ((0,m)) 的一条路径，并且路径上只会向上或者向右走。此外，对于任意两条分界线，它们之间互不跨越。

互不跨越如何处理？我们可以将其中一条路径平移，这样互不跨越就变成了互不相交。具体来说，原先的第 (i) 条线段，平移后的起点变成了 ((n-i+1,i-1)) ，终点变成了 ((m-i+1,i-1))。这样路径计数就变得易于处理了，我们可以直接套用 LGV 引理。

灰色表示路径的重叠部分，虚线表示平移后的路径

考虑处理 (a_{R,C}=V) 的限制。在平移前，这等价于 (P(R,C)) 的严格左下角恰好有 (V-1) 条路径经过。由于路径互不跨越，这就相当于第 (V-1) 经过了 (P) 的严格左下角且第 (V) 条路径经过了 (P) 的非严格右上角。

首先考虑第一条限制，我们可以直接将 (P) 按照第 (V-1) 条路径平移到 (P')，这样路径就被分成了“经过 (P') 严格左下角”和“没有经过 (P') 的严格左下角”两类，计算其中一种就可以推出另外一种，因此计算上无甚改变。而对于 (i<V-1)，LGV 引理可以保证第 (i) 条路径不与第 (V-1) 条路径相交，结果就是第 (i) 条路径也会经过 (P') 的严格左下角。因此，对于第 (i) 条路径，我们也可以类似于第 (V-1) 条计算。

再考虑第二条限制。注意到在平移之后，第 (V) 条路径只能经过 (P') 的严格右上角。这样一来，任何路径都不可能经过 (P')，所以我们建图的时候需要注意将经过 (P') 的方案去除。

但是，这里的讨论是基于“第 (V-1) 条路径经过 (P) 的严格左下角和第 (V) 条路径经过 (P) 的非严格右上角”的前提的，实际 LGV 的时候我们还没法保证这一点（因为 LGV 引理的前提为：所有路径都是平等的）。因此，我们需要引入形式变元 (x) 来刻画路径条数。这样，行列式的元素和结果都变成了多项式。考虑到多项式本身运算不便，我们可以计算对多项式代值后的结果，再插值得到原多项式。

这样，我们就得到了 (O(k^4)) 的算法。

小结：

1. 一开始对于问题的转化很巧妙。对于具有一定单调性的对象，我们都可以考虑勾勒出它的断点，并且研究断点；

   利用平移的方法，我们将路径的互不跨越变成了互不相交。

2. 仍然是利用单调性，将原先对于 (V-1) 条路径的讨论简化到了对于两条；

3. 注意细节，不能忽视第 (V) 条路径经过 (P) 的非严格右上角这一条件。

代码

#include <cstdio>
#include <utility>
#include <iostream>

#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 MAXK = 105, MAXN = 1005;

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 binom[MAXN][MAXN];

int val[MAXK], dp[MAXK], tmp[MAXK];

int coe[MAXK][MAXK][2];
int A[MAXK][MAXK];

int N, M, K, R, C, V;

inline int Qkpow( int, int );
inline int Mul( int x, int v ) { return 1ll * x * v % mod; }
inline int Inv( const int a ) { return Qkpow( a, mod - 2 ); }
inline int Sub( int x, int v ) { return ( x -= v ) < 0 ? x + mod : x; }
inline int Add( int x, int v ) { return ( x += v ) >= mod ? x - mod : x; }

inline int Qkpow( int base, int indx )/*{{{*/
{
	int ret = 1;
	while( indx )
	{
		if( indx & 1 ) ret = Mul( ret, base );
		base = Mul( base, base ), indx >>= 1;
	}
	return ret;
}/*}}}*/

inline void Init( const int n )/*{{{*/
{
	rep( i, 0, n )
	{
		binom[i][0] = binom[i][i] = 1;
		rep( j, 1, i - 1 ) binom[i][j] = Add( binom[i - 1][j], binom[i - 1][j - 1] );
	}
}/*}}}*/

int Gauss( const int n )/*{{{*/
{
	int ret = 1, idx, tmp, inv;
	for( int i = 1 ; i <= n ; i ++ )
	{
		idx = -1;
		for( int j = i ; j <= n ; j ++ )
			if( A[j][i] ) { idx = j; break; }
		if( idx == -1 ) return 0;
		if( idx ^ i ) 
			std :: swap( A[i], A[idx] ), ret = mod - ret;
		inv = Inv( A[i][i] );
		for( int j = i + 1 ; j <= n ; j ++ )
			if( ( tmp = Mul( inv, A[j][i] ) ) )
				for( int k = 1 ; k <= n ; k ++ )
					A[j][k] = Sub( A[j][k], Mul( tmp, A[i][k] ) );
	}
	rep( i, 1, n ) ret = Mul( ret, A[i][i] );
	return ret;
}/*}}}*/

std :: pair<int, int> Calc( const int n, const int m, const int r, const int c )/*{{{*/
{
	int fir = 0, sec = 0;
	if( r <= 0 || c <= 0 ) sec = 0;
	else if( r > n || c > m ) sec = binom[n + m][m];
	else
	{
		if( r <= c )
			rep( k, 0, r - 1 )
				sec = Add( sec, Mul( binom[n + c - r][n - k], binom[m - c + r][k] ) );
		else
			rep( k, 0, c - 1 )
				sec = Add( sec, Mul( binom[n - r + c][k], binom[m + r - c][m - k] ) );
	}
	fir = binom[n + m][m];
	if( 0 <= r && 0 <= c && r <= n && c <= m )
		fir = Sub( fir, Mul( binom[n - r + c][c], binom[m - c + r][r] ) );
	return std :: make_pair( Sub( fir, sec ), sec );
}/*}}}*/

int main()
{
	read( N ), read( M ), read( K );
	read( R ), read( C ), read( V );
	if( K == 1 ) return puts( "1" ), 0;
	Init( N + M ), R -= K - V, C -= K - V;
	rep( i, 1, K - 1 ) rep( j, 1, K - 1 )
	{
		int n = N + j - i, m = M + i - j;
		if( n < 0 || m < 0 ) continue;
		std :: pair<int, int> tmp = Calc( n, m, R - N + i - 1 + n, C + i - 1 );
		coe[i][j][0] = tmp.first, coe[i][j][1] = tmp.second;
	}
	rep( v, 1, K )
	{
		rep( i, 1, K - 1 ) rep( j, 1, K - 1 )
			A[i][j] = Add( coe[i][j][0], Mul( v, coe[i][j][1] ) );
		val[v] = Gauss( K - 1 );
	}
	dp[0] = 1;
	rep( i, 1, K )
		per( j, K, 0 )
		{
			dp[j] = Mul( dp[j], mod - i );
			if( j ) dp[j] = Add( dp[j], dp[j - 1] );
		}
	int ans = 0;
	rep( i, 1, K )
	{
		rep( j, 0, K ) tmp[j] = dp[j];
		rep( j, 0, K )
		{
			if( j ) tmp[j] = Sub( tmp[j], tmp[j - 1] );
			tmp[j] = Mul( tmp[j], Inv( mod - i ) );
		}
		int inv = val[i];
		rep( j, 1, K ) if( i != j )
			inv = Mul( inv, Inv( Sub( i, j ) ) );
		ans = Add( ans, Mul( inv, tmp[V - 1] ) );
	}
	write( ans ), putchar( '
' );
	return 0;
}