题解：P1386 座位安排

· · 题解

思路

依题 dp。

组合数学前面题解的 dl 已讲得清晰了，在这里不过多赘述。乘法原理。小学知识。

奉天承运,皇帝诏曰：

钦定 hzh 数组，hzh_i=后面“预定座位”的人数。故坐不下时，即当 hzh_i > n-i+1 时，应当挤挤凑合着坐判无解。

钦定 C 矩阵，C_j^i 表示从 \max(j,i) 个数中选 \min(j,i) 个数的方法和。易转移如下：C_j^i=(C^{i-1}_{j-1}+C^{i-1}_j)。

钦定 dp 矩阵，dp_j^i 表示在编号大于等于 i 的人中确定 j 人之座位的方法总和数。易转移如下：dp_j^i=\sum_{k=0}^j dp_{j-k}^{i-1}\times C_k^j。

敬告众卿：勿忘取 %。

码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
void dui(int x)
{
    cout<<"YES"<<" "<<x<<endl;
}
void cuo()
{
    cout<<"NO"<<endl;
}
int hzh[305],c[305][305],dp[305][305];
signed main()
{
    int  t;
    cin>>t;
    while(t--)
    {
        int n,m,mod;
        cin>>n>>m>>mod;
        bool flag=0;
        memset(hzh,0,sizeof(hzh));
        memset(dp,0,sizeof(dp));
        for(int i=0;i<=300;i++)
        {
            c[i][0]=c[i][i]=1;
            for(int j=1;j<=i;j++)   c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;

        }
        for(int i=1;i<=m;i++)
        {
            int x;
            cin>>x;
            int y;
            cin>>y;
            hzh[y]++;
        }
        for(int i=n;i>=1;i--)   hzh[i]+=hzh[i+1];
        for(int i=1;i<=n;i++)
        {
            if(hzh[i]>n-i+1)
            {
                cuo();
                flag=1;
                break;
            }
        }
        if(flag==1) continue;
        for(int i=0;i<=n;i++)
        {
            if(i)   dp[n+1][i]=0;
            else    dp[n+1][i]=1;
        }
        for(int i=n;i>=1;i--)
        {
            for(int j=0;j<=n-i+1-hzh[i]&&j>=0;j++)
            {
                for(int k=0;k<=j;k++) 
                {
                    dp[i][j]=(dp[i][j]+c[j][k]*dp[i+1][j-k])%mod;
                }
            }
        }
        dui(dp[1][n-m]);
    }
}