题目

分析

可以想到用 DP 解决。

由于把空位放到状态里面太麻烦了，因此我们单独将 " 组 " 提出来进行 DP 。

\(f(i,j)\)：前\(i\)个人组成\(j\)个组的方案数。

此时这个组是有顺序有编号的，并且按照编号相邻（由于在环上，\(j\) 组和 \(1\) 组也算相邻）。

考虑三种转移：

1.我们新建一组，并在原来的一个组后面插入新组：\(f(i+1,j+1)+=j*f(i,j)\)；

2.我们将新的人安排到新的组里面，可以放在组的两头：\(f(i+1,j)+=2j*f(i,j)\)；

3.我们用一个人将两个组合在一起，有\(j\)个组相邻：\(f(i+1,j-1)+=j*f(i,j)\)；

可以发现这样 DP 只需要保证中途状态不会超过\(G\)组即可。

环上问题，我们可以先固定第一个人的位置，计算出方案数然后再乘上\(n\)。因此\(f(1,1)=1\)。

现在考虑怎么再组与组之间插入空位组成结果。设现在分配\(g\)个组，第\(i\)个组后有\(x_i\)个空位，则可以得到：

\[\sum_{i=1}^g x_i=n-k\ |x_i\ge 1
\]

这是一个可用插板法解决的问题，因此可以快速计算方案数。

因此一般情况的答案为：

\[\sum_{i=1}^G f(k,i)\times C_{n-k-1}^{i-1}
\]

但是如果\(n=k\)，则组合数下标为\(-1\)，不能算。这实际上是位置会被坐满，只有一个组的情况。当第\(k\)个人入座的时候，他只可能有一个位置可坐，因此方案数为\(n\times f(k-1,1)\)。

代码

#include <cstdio>

const int mod = 1e9 + 7;

const int MAXN = 2005;

template<typename _T>

void read( _T &x )

{

	x = 0;char s = getchar();int f = 1;

	while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}

	while( s >= '0' && 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 ) + 1; }

	if( 9 < x ){ write( x / 10 ); }

	putchar( x % 10 + '0' );

}

int f[MAXN][MAXN], C[MAXN][MAXN];

int N, K, G;

void upt( int &x, const int v ) { x = ( x + v ) % mod; }

void init()

{

	C[0][0] = 1;

	for( int i = 1 ; i <= N ; i ++ )

	{

		C[i][0] = C[i][i] = 1;

		for( int j = 1 ; j < i ; j ++ ) C[i][j] = ( C[i - 1][j] + C[i - 1][j - 1] ) % mod;

	}

}

class Seatfriends

{

	public:

	int countseatnumb( const int n, const int k, const int g )

	{

		N = n, K = k, G = g;

		init();

		f[1][1] = 1;

		for( int i = 1 ; i < K ; i ++ )

			for( int j = 1 ; j <= G ; j ++ )

			{

				upt( f[i + 1][j], 2ll * j * f[i][j] % mod );

				upt( f[i + 1][j + 1], 1ll * j * f[i][j] % mod );

				if( j > 1 ) upt( f[i + 1][j - 1], 1ll * j * f[i][j] % mod );

			}

		int ans = 0;

		if( N == K ) return 1ll * f[K - 1][1] * N % mod;

		for( int i = 1 ; i <= G ; i ++ )

			upt( ans, 1ll * f[K][i] * ( N == K ? 1 : C[N - K - 1][i - 1] ) % mod );

		return 1ll * ans * N % mod;

	}

};

巴特西

[TopCoder]Seatfriends

题目

分析

代码

最新文章

热门文章