|
传送门
题目描述
给 nn 个人安排座位，先给每个人一个 1\thicksim n1～n 的编号，设第 ii 个人的编号为 a_ia
i
?
（不同人的编号可以相同）。
接着从第一个人开始，大家依次入座，第 ii 个人来了以后尝试坐到 a_ia
i
?
，如果 a_ia
i
?
被占据了，就尝试 a_i+1a
i
?
+1，a_i+1a
i
?
+1 也被占据了的话就尝试 a_i+2a
i
?
+2……，如果一直尝试到第 nn 个都不行，该安排方案就不合法。
然而有 mm 个人的编号已经确定（他们或许贿赂了你的上司…），你只能安排剩下的人的编号，求有多少种合法的安排方案。
由于答案可能很大，只需输出其除以 MM 后的余数即可。
输入格式
第一行一个整数 TT，表示数据组数。
对于每组数据，第一行有三个整数，分别表示 nn、mm、MM。
若 mm 不为 00，则接下来一行有 mm 对整数，p_1p
1
?
、q_1q
1
?
，p_2p
2
?
、q_2q
2
?
，…， p_mp
m
?
、q_mq
m
?
，其中第 ii 对整数 p_ip
i
?
、q_iq
i
?
表示第 p_ip
i
?
个人的编号必须为 q_iq
i
?
。
输出格式
对于每组数据输出一行，若是有解则输出 YES，后跟一个整数表示方案数 \bmod MmodM，注意，YES 和数之间只有一个空格，否则输出 NO。
输入输出样例
输入 #1复制
2
4 3 10
1 2 2 1 3 1
10 3 8882
7 9 2 9 5 10
输出 #1复制
YES 4
NO
说明/提示
数据规模与约定
对于 100%100% 的数据，保证
1 \leq T \leq 101≤T≤10。
1 \leq n \leq 3001≤n≤300， 0 \leq m \leq n0≤m≤n， 2 \leq M \leq 10^92≤M≤10
9
。
1 \leq p_i1≤p
i
?
、q_i \leq nq
i
?
≤n。
p_ip
i
?
互不相同。
上代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#define int long long
using namespace std;
inline int read(){
int x=0,w=0;char c=getchar();
while(!isdigit(c))w|=c=='-',c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return w?-x:x;
}
namespace star
{
const int maxn=305;
int n,m,mod,f[maxn][maxn],C[maxn][maxn],sum[maxn];
inline void work(){
memset(sum,0,sizeof sum);
memset(f,0,sizeof f);
n=read(),m=read(),mod=read();
for(int i=1;i<=m;i++)read(),sum[read()]++;
for(int i=n;i;i--){
sum[i]+=sum[i+1];
if(sum[i]>n-i+1)return (void)puts("NO");
}
for(int i=0;i<=n;i++)C[i][0]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
f[n+1][0]=1;
for(int i=n;i;i--)
for(int j=0;j<=n-sum[i]-i+1;j++)
for(int k=0;k<=j;k++)f[i][j]+=f[i+1][j-k]*C[j][k]%mod,f[i][j]%=mod;
printf("YES %lld\n",f[1][n-m]);
}
}
signed main(){
int T=read();
while(T--)star::work();
return 0;
}
|