传送门

先考虑如何判断无解，设 $sum[i]$ 表示确定的人中，编号大于 $i$ 的人的人数

如果 $sum[i]>n-i+1$ 则无解，进一步考虑设 $f[i][j]$ 表示当前确定完编号大于等于 $i$ 的人，除去原本固定的人还有 $j$ 人已经确定

那么有 $f[i][j]=\sum_{k=0}^{j}f[i+1][j-k] \cdot C_{j}^{k},j \in [0,n-i+1-sum[i]]$

表示在确定 $j-k$ 人的编号的情况下，再选 $k$ 个人编号为 $i$，乘上组合数是因为每个人都是不同的，我们可以在 $j$ 个人中任意选择 $k$ 个编号为 $i$

记得组合数每次都要重新算，因为模数不同…

#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
inline int read()
{
int x=,f=; char ch=getchar();
while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }
while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); } return x*f; } const int N=; int T,n,m,mo,sum[N]; ll C[N][N],f[N][N]; inline ll fk(ll x) { return x>=mo ? x-mo : x; }
int main()
{
T=read();
while(T--)
{
memset(f,,sizeof(f)); int a,b,flag=;
memset(sum,,sizeof(sum));
n=read(),m=read(),mo=read();
for(int i=;i<=m;i++) { a=read(),b=read(); sum[b]++; } for(int i=n;i;i--) { sum[i]+=sum[i+]; if(sum[i]>n-i+) { flag=; break; }
}
if(!flag) { printf("NO\n"); continue; }
// f[i][j]+=f[i+1][j-k]*C[j][k]
for(int i=;i<=;i++) { C[i][]=; for(int j=;j<=i;j++) C[i][j]=fk(C[i-][j]+C[i-][j-]); } f[n+][]=; for(int i=n;i>=;i--)
for(int j=;j<=n-i+-sum[i];j++)
for(int k=;k<=j;k++)
f[i][j]=fk(f[i][j]+f[i+][j-k]*C[j][k]%mo);
printf("YES %lld\n",f[][n-m]);
}
return ;
}