题目描述
给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
输入输出样例
2 4 3 10 1 2 2 1 3 1 10 3 8882 7 9 2 9 5 10
YES 4 NO
说明/提示
100%的数据满足：1≤T≤10，1≤n≤300，0≤m≤n，2≤M≤10^9，1≤pi、qi≤n 且保证pi互不相同。
思路：
首先需要证明一个前提：当且仅当一个序列从小到大排序的第i项小于等于i对i从1到N恒成立，该序列合法，否则不合法。①
比如说1 1 3 4 5合法，1 3 3 4 5不合法。
丝毫不严谨的证明：显然1 2 3 4 5合法，且1 1 3 4 5优于1 2 3 4 5，所以1 1 3 4 5必然合法
如果不满足①，则必然可以找到一个位置使得第i项大于i，则包括此位置在内的后缀序列（例如上个例子就是3 3 4 5）就会出现人数比座位数多的情况，显然不合法。
同时可以看到，序列是否合法只与构成有关，与排序无关。
定义状态dp[ x ] [ y ]表示对前 x 个位置，自己安排（不包括钦定）的人数有 y 人的方案总数。
则有 dp[ 0 ] [ 0 ] = 1，dp[ i ] [ j ] =∑ dp[ i - 1] [ k ] + c[ n - m - k ] [ j - k ]
其中 j>=i-num[ i ] ，j >= k >= i-1 - num[i-1]
num [ i ] 表示前 i 个编号的座位被强制钦定的人数
c是预处理的组合数数组
代码：（好丑）
#include <cstdio> #include <cstring> #include <iostream> #define int long long using namespace std; const int maxn=305; int loc,temp; int n,m,MOD; int vis[maxn]; int num[maxn]; int dp[maxn][maxn]; int c[maxn][maxn]; inline void init(int n,int MOD) { c[0][0]=1; for (int i=1;i<=n;i++) { for (int j=0;j<=i;j++) { c[i][j]=c[i-1][j]+c[i-1][j-1]; c[i][j]%=MOD; } } } inline void work(){ dp[0][0]=1; for (int i=1;i<=n;i++) { for (int j=i-num[i];j<=n-m;j++) {//j为本次转移后安排的人数（不包括钦定人数） for (int k=j;k>=i-1-num[i-1];k--) {//k为上一次安排人数，则x=j-k为本次安排人数，需满足 <x< int res=n-m-k;//可调用人数 dp[i][j]+=dp[i-1][k]*c[res][j-k]; dp[i][j]%=MOD; } } } printf("%lld\n",dp[n][n-m]); } signed main(){ int T; scanf("%lld",&T); while (T--) { memset(dp,0,sizeof(dp)); memset(num,0,sizeof(num)); memset(vis,0,sizeof(vis)); memset(c,0,sizeof(c)); scanf("%lld%lld%lld",&n,&m,&MOD); init(n,MOD); for (int i=1;i<=m;i++) { scanf("%lld%lld",&temp,&loc); vis[loc]++; } bool flag=0; for (int i=n;i>=1;i--) { num[i]=num[i+1]+vis[i]; if (num[i]>n-i+1) { printf("NO\n"); flag=1; break; } } if (flag) continue; memset(num,0,sizeof(num)); for (int i=1;i<=n;i++) num[i]=num[i-1]+vis[i]; printf("YES "); work(); } }