洛谷P2523 Problem c

传送门

题目描述

给 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
#include
#include
#include
#include
#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41