「校内 OJ」Seats

题目

一张圆形餐桌有 \(2n\) 个座位,现在有 \(n\) 对夫妻入座,要求男女隔位就坐,且一对夫妻不能相邻;

如果某种入座方案可以通过旋转得到另一种方案,则它们是本质相同的。求本质不同方案数。

数据范围:对于 \(100\%\) 的数据,满足 \(1\le n\le 10^5\),答案对 \(998244353\) 取模。

分析

其实就是经典的“围坐问题”。

首先注意到,我们可以先确定女性的座位,而后确定男性的座位。这样对于任意的女性入座方案,男性的方案数相同;而本质不同的女性入座方案即圆排列方案,为 \((n-1)!\)

考虑固定女性后男性的入座方案,这个问题等价于计算 \(p_i\not=i\)\(p_i\not=(i\bmod n+1)\)\(\{1,2,\dots, n\}\) 的排列个数。这个问题很类似于错排,它也有一个名字——“二重错排”。

错排的一种计算方式为容斥,我们同样尝试容斥。那么对于位置 \(i\),它的性质为“\(P_i\)\(p_i=i\) 或者 \(p_i=(i\bmod n+1)\)”,我们需要计算每个位置都不满足性质的方案数。

任意选择一个位置考虑,比如位置 1。如果 \(p_1=1\),那么 \(p_n\) 要想满足性质,则 \(p_n=n\),而 \(p_2\) 则不受影响;反过来,\(p_1=2\) 的情况也很类似。这启示我们将一个位置拆成相邻的两个位置,这样 \(p_i=i\) 就对应选择靠前的位置 \(i\),而 \(p_i=(i\bmod n+1)\) 则对应选择靠后的位置 \(i\)。那么此时选择方案的相互影响可以被简单地描述为“没有相邻的位置被选择”。

那么问题就变成了求“从环上的 \(2n\) 个元素中选取 \(k\) 个不相邻元素”的方案数,这是一个经典问题,结果为 \(\binom{2n-k+1}{k}-\binom{2n-k-1}{k-2}\),具体推导过程见下:

首先考虑从长度为 \(n\) 的序列中选取 \(k\) 个不相邻元素的方案数。

假设序列为 \(\{1,2,\dots,n\}\),那么任意选取会得到 \(a_1,a_2,\dots,a_k\),满足 \(a_i> a_{i-1},1<i\le k\)

现在要求不相邻,就是要求 \(a_i>a_{i-1}+1\Leftrightarrow a_i-a_{i-1}>1\)

相邻项差值的常规变化是通过做差化掉:设 \(b_i=a_i-i\),那么就有 \(b_i>b_{i+1}\)。可以发现合法的 \(a,b\) 是双射关系,而 \(b\) 就相当于从序列 \(\{0,1,2,\dots,n-k\}\) 中选取 \(k\) 个元素,自然得到方案数为 \(\binom{n-k+1}{k}\)


考虑环上的情况,从某个位置破环,问题变成了序列方案数减去首尾都被选中的方案数。

那么不难得到结果就是 \(\binom{n-k+1}{k}-\binom{n-4-(k-2)+1}{k-2}=\binom{n-k+1}{k}-\binom{n-k-1}{k-2}\)

所以答案就是:

\[(n-1)!\sum_{k=0}^n(-1)^k\left(\binom{2n-k+1}{k}-\binom{2n-k-1}{k-2}\right)(n-k)! \]

小结:

  1. 如果觉得容斥难以下嘴,可以从最基础的方式入手,找出每个元素的“性质”是什么;

  2. 分析容斥方案的时候,从问题表现的性质入手,尝试构造出一种简洁的模型;

  3. 注意一下“经典问题”推导中,等差的化简方式;

代码

#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 MAXN = 1e6 + 5;
const int mod = 998244353;

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

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 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 ) ret = Mul( ret, base );
		base = Mul( base, base ), indx >>= 1;
	}
	return ret;
}

inline void Init( const int n = 5e5 )
{
	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()
{
	read( N ), Init();
	int ans = 0, res;
	rep( i, 0, N )
	{
		res = C( 2 * N - i + 1, i );
		if( i >= 2 ) res = Sub( res, C( 2 * N - i - 1, i - 2 ) );
		res = Mul( res, fac[N - i] );
		ans = i & 1 ? Sub( ans, res ) : Add( ans, res );
	}
	write( Mul( ans, fac[N - 1] ) ), putchar( ‘\n‘ );
	return 0;
}

「校内 OJ」Seats

上一篇:gitee提交过程


下一篇:线段树模板(区间修改+区间查询)