P2523 [HAOI2011]Problem c DP+组合

题意:

给 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方程。

  1. \(s[i]\)表示编号大于等于\(i\)的人的个数,对于有解的情况必定满足对于任意的\(1\leq i \leq n, s[i]\leq (n-i+1)\)因为编号为\(i\)以后的凳子只有\(n-i+1\)

  2. \(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;
    }
    
原文地址:https://www.cnblogs.com/youth518/p/13650139.html