P1386 座位安排

​​傳送門​​

題意：

思路：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define pb push_back 
#define p push
ll mod = 998244353;
ll vis[310],b[310];
ll dp[310][310];
ll c[310][310];

int main()
{
  int t;
  cin>>t;
  while(t--)
  {
    memset(b,0,sizeof(b));
    memset(dp,0,sizeof(dp));
    memset(vis,0,sizeof(vis));
    ll n,m,flag;
    cin>>n>>m>>mod;
    for(int i = 0; i <= 301; 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;
      }
    }
    flag = 1;
    for(int i = 1; i <= m; i++)
    {
      int x,y;
      cin>>x>>y;
      vis[y]++;
    }
    for(int i = n; i >= 1; i--)
    {
      b[i] = b[i+1]+vis[i];
      if(b[i] > n-i+1)
      {
        flag = 0;
        break;
      }
    }
    if(!flag)cout<<"NO\n";
    else
    {
      dp[n+1][0] = 1;
      for(int i = n; i >= 1; i--)
      {
        for(int j = 0; j <= n-i+1-b[i]; j++)
        {
          for(int k = 0; k <= j; k++)
          {
            dp[i][j] = (dp[i][j] + dp[i+1][j-k]*c[j][k]%mod)%mod;
          }
        }
      }
      cout<<"YES"<<" "<<dp[1][n-m]<<endl;
    }
  }
}