给n个人安排座位，先给每个人一个1~n的编号，设第i个人的编号为ai（不同人的编号可以相同），接着从第一个人开始，大家依次入座，第i个人来了以后尝试坐到ai，如果ai被占据了，就尝试ai+1，ai+1也被占据了的话就尝试ai+2，……，如果一直尝试到第n个都不行，该安排方案就不合法。然而有m个人的编号已经确定(他们或许贿赂了你的上司...)，你只能安排剩下的人的编号，求有多少种合法的安排方案。由于答案可能很大，只需输出其除以M后的余数即可。
输入格式：
第一行一个整数T，表示数据组数
对于每组数据，第一行有三个整数，分别表示n、m、M
若m不为0，则接下来一行有m对整数，p1、q1，p2、q2 ,…, pm、qm，其中第i对整数pi、qi表示第pi个人的编号必须为qi
输出格式：
对于每组数据输出一行，若是有解则输出YES，后跟一个整数表示方案数mod M，注意，YES和数之间只有一个空格，否则输出NO
——————————————————————————————————
#include<bits/stdc++.h> using namespace std; int a,b,t,n,m,M; int bol[3000],f[1000][1000],cc[1000][1000]; int main() { cin>>t; while(t--){ memset(bol,0,sizeof(bol));memset(f,0,sizeof(f)); cin>>n>>m>>M; for(int i=1;i<=m;i++){cin>>a>>b;bol[b]++;} int flag=0; for(int i=n;i;i--) {bol[i]+=bol[i+1];if(bol[i]>n-i+1){flag=1;break;}} if(flag){cout<<"NO"<<endl;continue;} for (int i = 0; i <= n; ++i) cc[i][0] = 1; for (int i = 1; i <= n; ++i) for (int j = 1; j <= i; ++j) cc[i][j] = (cc[i - 1][j] + cc[i - 1][j - 1]) % M; f[n+1][0]=1; for(int i=n;i;i--) for(int j=0;j<=n-bol[i]-i+1;j++) for(int k=0;k<=j;k++) f[i][j]=((long long)f[i][j]+(long long )f[i+1][j-k]*cc[j][k])%M; cout<<"YES "<<f[1][n-m]<<endl; } }
原文：https://www.cnblogs.com/SFWR-YOU/p/10926868.html