题意:
给 n 个人安排座位,先给每个人一个 \(1\thicksim n\) 的编号,设第i 个人的编号为 \(a_i\)(不同人的编号可以相同)。
接着从第一个人开始,依次入座,第 i 个人来了以后尝试坐到\(a_i\),如果 \(a_i\) 被占据了,就尝试 \(a_{i+1}\),若\(a_{i+1}\)也被占据了的话就尝试\(a_{i+2}\) ……,如果一直尝试到第 n 个都不行,该安排方案就不合法。
然而有 m个人的编号已经确定,你只能安排剩下的人的编号,求有多少种合法的安排方案模M。
范围&性质:\(1\leq T\leq 10\),\(1\leq n,m\leq 300,2\leq M\leq 10^9,1\leq p_i,q_i\leq n\)
分析:
分析题意可以得到,对于不同编号的排列,可能得到的座位结果是相同的,所以我们考虑用编号构造DP方程。
-
记\(s[i]\)表示编号大于等于\(i\)的人的个数,对于有解的情况必定满足对于任意的\(1\leq i \leq n, s[i]\leq (n-i+1)\)因为编号为\(i\)以后的凳子只有\(n-i+1\)个
-
记\(f[i][j]\)表示剩余\(n-m\)个人中,已经确定了\(j\)个人,编号大于等于\(i\)可以得到转移方程如下:
$$ f[i][j]=f[i+1][j-k]\times C_{j}^{k} (0\leq k\leq n-i+1-s[i]) $$
整体的时间复杂度为\(\omicron(Tn^3)\)的
代码:
#include<bits/stdc++.h> using namespace std; namespace zzc { long long c[305][305],sum[305],f[305][305]; long long t,n,m,mod; void work() { scanf("%lld",&t); while(t--) { bool flag=false; memset(sum,0,sizeof(sum)); memset(f,0,sizeof(f)); scanf("%lld%lld%lld",&n,&m,&mod); for(int i=1;i<=m;i++) { long long x,tmp; scanf("%lld%lld",&x,&tmp); sum[tmp]++; } for(int i=n;i>=1;i--) { sum[i]+=sum[i+1]; if(sum[i]>n-i+1) { printf("NO\n"); flag=true; break; } } if(flag) continue; c[0][0]=1; c[1][1]=c[1][0]=1; for(int i=2;i<=n;i++) { c[i][0]=1; for(int j=1;j<=i;j++) { c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod; } } f[n+1][0]=1; for(int i=n;i>=1;i--) { for(int j=0;j<=n-sum[i]-i+1;j++) { for(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]); } } } int main() { zzc::work(); return 0; }