P2523 [HAOI2011]Problem c/ P1386 座位安排

文章目录

R e s u l t Result Result

好家伙，双倍经验，连数据都一模一样呢

---

H y p e r l i n k Hyperlink Hyperlink

https://www.luogu.com.cn/problem/P1386
https://www.luogu.com.cn/problem/P2523

---

D e s c r i p t i o n Description Description

有 n n n个人排座位，如果第 i i i个人座位被占了，则它会坐在这个位置后面的第一个没被占的位置 [ i + 1 , n ] [i+1,n] [i+1,n]，如果没有，则这种方案是不合法的

现在有 m m m个人已经钦定了它们的座位，问合法的坐座位方案数，答案对 M M M取模

数据范围： n , m ≤ 300 , M ≤ 1 0 9 n,m\leq 300,M\leq 10^9 n,m≤300,M≤109

---

S o l u t i o n Solution Solution

首先座位的钦定与具体是哪个人无关，我们只关心还剩下多少的座位

那么就可以 d p dp dp了， l a s t i last_i lasti​表示 i i i这个位置后面还剩余多少位置（包括 i i i），容易发现对位置做一个后缀和即可得到 l a s t i = n − i + 1 − s u m i last_i=n-i+1-sum_i lasti​=n−i+1−sumi​

设 f i , j f_{i,j} fi,j​表示排到了第 i i i个座位（倒着排），后面已经有 j j j个人确定了位置

初态： f n + 1 , 0 = 1 f_{n+1,0}=1 fn+1,0​=1
转移： f i , j = ∑ j = 0 l a s t i ∑ k = 0 j f i + 1 , j − k C j k f_{i,j}=\sum_{j=0}^{last_i}\sum_{k=0}^j f_{i+1,j-k}C_j^k fi,j​=∑j=0lasti​​∑k=0j​fi+1,j−k​Cjk​
终态： f 1 , n − m f_{1,n-m} f1,n−m​

注意特判 l a s t i < 0 last_i<0 lasti​<0的情况，这样是不可能排得了座位的

时间复杂度： O ( T n 3 ) O(Tn^3) O(Tn3)

---

C o d e Code Code

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define LL long long
#define N 310
using namespace std;int n,m,mod,T;
LL f[N][N],s[N],C[N][N];
inline LL read()
{
	LL d=1,f=0;char c;
	while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48;
	while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;
	return d*f;
}
inline bool tp(){for(register int i=1;i<=n;i++)if(s[i]>n-i+1) return true;return false;}
signed main()
{
	T=read();
	while(T--)
	{
		memset(f,0,sizeof(f));
		memset(s,0,sizeof(s));
		n=read();m=read();mod=read();
		C[0][0]=C[1][0]=C[1][1]=1;
		for(register int i=2;i<=n;i++){C[i][0]=1;for(register int j=1;j<=i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;}
		for(register int i=1;i<=m;i++) read(),s[read()]++;
		for(register int i=n;i;i--) s[i]+=s[i+1];
		if(tp()) {puts("NO");continue;}
		f[n+1][0]=1;
		for(register int i=n;i;i--) for(register int j=0;j<=n-i+1-s[i];j++) for(register int k=0;k<=j;k++)
		f[i][j]=(f[i][j]+f[i+1][j-k]*C[j][k]%mod)%mod;
		printf("YES %lld\n",f[1][n-m]);
	}
}