[HAOI2001] problem c 解题报告

解题报告 各省省选

---

题目链接

题目大意

为 n 个人编排位置，不同的人的位置编号可以相同。n 个人会依次去找自己的位置，设第 $i$ 个人的位置编号为 $a_i$，若 $a_i$ 已经有人坐了，则这个人会去找 $a_i$ 后的位置，找到一个空的位置马上坐下来，若有人无法坐下来，则这个方案是不合法的。
现有 $m$ 个人，他们的位置已经确定了，求编排位置的方案数。
若没有合法的方案，则输出 NO，
否则输出 YES + 合法方案数。

思路

对于判断是否有合法的方案数，可以先计算出每个位置已经安排的人数的后缀和 $sum[i]$，若 $sum[i]>n-i+1$，则不可能有合法的方案。

对于统计方案数，考虑dp。
设 $f[i][j]$ 为（从后往前）考虑到第 $i$ 个位置，已经为 $j$ 个人安排位置的方案数，转移方程为：

$$f[i][j]+=f[i+1][k]*C$$
$C$ 为一个组合数，表示当前选 $j-k$ 个人的方案数，现在我们就需要考虑 $C$ 的取值。
若没有预先安排好位置的人（即 m 等于 0）时，$C$ 显然取 $C_{n-k}^{j-k}$，但是由于已经有人预先安排好位置了，所以有一些方案是不能选的。
设 $bur[i]$ 表示预先安排好位置的人中，把位置安排在 $i$ 的人数，那么位置 $i$ 实际上需要安排的人数就是 $j-k-bur[i]$，可安排在位置 $i$ 的人数也不是 $n-k$ ，而是 $n-k-(m-sum_{bur[i+1]})$ 。
为什么是减去 $m-sum_{bur[i]}$，而不是减去 $m$ 呢，因为在考虑到位置 $i$ 时，总共是有 $n-k$ 个人还没安排位置，而这 $n-k$ 个人中已经预先安排好位置的人数是 $m-sum_{bur[i+1]}$，而不是 $m$，所以应当减去$m-sum_{bur[i]}$。
所以最终的转移方程为
$$f[i][j]+=f[i+1][k]*C_{n-k-(m-sum_{bur[i+1]})}^{j-k-bur[i]}$$
（注：这里的 $sum$ 表示的是后缀和。）

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long long
using namespace std;
const int N=300+7;
int T,n,m,bur[N],lim[N];
ll mod,f[N][N],c[N][N];
void init(){
    c[0][0]=c[1][0]=c[1][1]=1;
    for(int i=2;i<=n;i++)
        for(int j=0;j<=i;j++)
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
}
int main(){
    //freopen("pc.in","r",stdin);
    cin>>T;
    while(T--){
        memset(f,0,sizeof(f));
        memset(bur,0,sizeof(bur));
        memset(c,0,sizeof(c));
        scanf("%d%d%lld",&n,&m,&mod);
        init();
        int x,q;
        for(int i=1;i<=m;i++){
            scanf("%d%d",&x,&q);
            bur[q]++;
        }
        int res=0; bool flag=0;
        for(int i=n;i>=1;i--){
            res+=bur[i];
            if(res>n-i+1){
                printf("NO\n");
                flag=1;break;
            }
        }
        if(flag) continue;
        f[n+1][0]=1;
        for(int i=n;i>=1;i--){
            lim[i]=n-i+1;
            for(int j=bur[i+1]+bur[i];j<=lim[i];j++)
                for(int k=bur[i+1];k<=min(j-bur[i],lim[i+1]);k++)
                    f[i][j]=(f[i][j]+f[i+1][k]*c[n-k-m][j-k-bur[i]]%mod)%mod;
            m-=bur[i];
        }
        printf("YES %lld\n",f[1][n]);
    }
    return 0;
}