题目
一张圆形餐桌有 \(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}\)。
所以答案就是：
小结：
-
如果觉得容斥难以
下嘴，可以从最基础的方式入手，找出每个元素的“性质”是什么； -
分析容斥方案的时候，从问题表现的性质入手，尝试构造出一种简洁的模型；
-
注意一下“经典问题”推导中，等差的化简方式；
代码
#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;
}