OI - Seatfriends (Topcoder) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI - Seatfriends (Topcoder)

发表于 更新于 分类于 Valine：

失败是无可原谅，成功是理所应当……对吗？

# 题目

> Vjudge

有 $N$ 只椅子排成一个环，现在来了 $M$ 个人，依次选择一个空的位置入座。一个“段”为最长的已经有人的连续一段椅子。

要求任意时刻，段的数量不超过 $G$。求最后入座的情况的方案数，两种入座情况被视作不同当且仅当存在至少一个椅子，椅子上坐的人不同（人有编号）。

答案对 $10^9+7$ 取模。

# 解析

发现因为有空位置，并不好处理“任意时刻段数不超过 $G$” 的限制。因此想到先忽略掉空位置，只考虑 $M$ 个人入座，形成若干段，保证段数不超过 $G$。

那么可以 DP，f[i][j] 表示前 $i$ 个人入座，形成了 $j$ 个段的方案数。按照这个定义，初始状态为“第一个人入座形成一个段”，而且第一个人有 $n$ 个位置可以选：f[1][1]=n。

考虑转移，当第 $i+1$ 个人入座时：

  1. 新形成一个段：这个新形成的段的位置可以在任意两个已有的段之间，共 $j$ 个可选位置 —— f[i+1][j+1]+=f[i][j]*j
  2. 放在两个段之间合并成为一个段（需要保证至少有两个段），共 $j$ 个可选位置 —— f[i+1][j-1]+=f[i][j]*j

  3. 放在任意一个段的前/后，共 $j$ 段，每个段可以放在前或后（2种）—— f[i+1][j]+=f[i][j]*2*j

    > Tab.

    有特殊情况是 $M=N$ 时，放最后一个人的时候只存在一种放法，因为此时只剩一个段，而且段前面的位置和段后面的位置是同一个。即 i+1=n 时 f[i+1][j-1]+=f[i][j]*j

最后考虑把空位放到各个段之间，枚举最后的段数 $j$：

段与段之间必须有空位，相当于 $j$ 个盒子；剩下 $n-m$ 个空位放在段与段之间，相当于 $n-m$ 个球；要求每个盒子不空，那么运用隔板法就知道方案数为 $C_{n-m-1}^{j-1}$，则 $ans=\sum\limits_{j=1}^{G}f[m][j]\times C_{n-m-1}^{j-1}$。

> Tab.

$N=M$ 仍然是特殊情况，此时没有空位，实际上是个圆排列。对于圆排列，确定了前 $m-1$ 个人的入座情况后，第 $m$ 个人只能坐剩下的那个位置了，所以方案数为 f[m-1][1]。

# 源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=2000,MOD=1e9+7;

int Add(int a,int b){return a+b>=MOD? a+b-MOD:a+b;}
int Sub(int a,int b){return a-b<0? a-b+MOD:a-b;}
int Mul(int a,int b){return 1ll*a*b%MOD;}
int ExAdd(int &a,int b){return a=Add(a,b);}
int ExMul(int &a,int b){return a=Mul(a,b);}
int QPow(int a,int b){
    int ret=1;
    while(b){
        if(b&1) ExMul(ret,a);
        ExMul(a,a);
        b>>=1;
    }
    return ret;
}

int dp[N+3][N+3];
int fac[N+3],inv[N+3];

class Seatfriends{
public:
    void Prepare(){
        fac[0]=1;
        for(int i=1;i<=N;i++)
            fac[i]=Mul(fac[i-1],i);
        inv[N]=QPow(fac[N],MOD-2);
        for(int i=N-1;i>=0;i--)
            inv[i]=Mul(inv[i+1],i+1);
    }
    int funC(int a,int b){return a<=b? Mul(fac[b],Mul(inv[a],inv[b-a])):0;}
    int countseatnumb(int n,int m,int lim){
        Prepare();
        dp[1][1]=n;
        for(int i=1;i<m;i++)
            for(int j=1;j<=lim;j++){
                if(!dp[i][j]) continue;
                //1. 单独开一组
                if(j+1<=lim)
                    ExAdd(dp[i+1][j+1],Mul(dp[i][j],j));
                //2. 把两组合并
                if(j>1)
                    ExAdd(dp[i+1][j-1],Mul(dp[i][j],j));
                //3. 单独贴到一组的前后
                ExAdd(dp[i+1][j],Mul(dp[i][j],Mul(i+1==n? 1:2,j)));
            }
        int ret=0,emp=n-m;
        if(emp)
            for(int j=1;j<=lim;j++){
                int add=Mul(funC(j-1,emp-1),dp[m][j]);
                ExAdd(ret,add);
            }
        else
            ret=dp[m-1][1];
        return ret;
    }
};

THE END

Thanks for reading!