牛客练习赛71 C- 数学考试 DP

牛客练习赛71 C- 数学考试

题意

求 $1\sim n$ 的排列，有 $m$ 个限制条件，第 $i$ 个限制条件 $p_i$ 表示前 $p_i$ 个数不能是 $1\sim p_i$ 的排列，求符合要求的排列的个数。答案对 20000311 取模。

$n\le 2000,m,p_i<n$

做法1

设 $dp[i][j]$ 为满足限制的情况下放好了排列的前 $i$ 个数且最大值为 $j$ 的方案数，转移如下：

$i=j=p_k,k \in [1,m]$ ，说明这一位有限制 $dp[i][j]=0$ 。
否则， $dp[i][j]=\sum_{k=1}^{j-1}dp[i-1][k]+dp[i-1][j] \cdot (j-i+1)$ ，表示若 $k<j$ ，那么第 $i$ 位只能放一种数 $j$ ，若 $k=j$ ，第 $i$ 位可以放 $j-i+1$ 种数，前面的部分可以前缀和优化。

复杂度为 $O(n^2)$ 。

做法2

设 $dp[i]$ 为放置前 $p[i]$ 个数满足前 $i-1$ 个限制，但是不满足第 $i$ 个限制的方案数。

$dp[i]=p[i]!-\sum_{j=1}^{i-1}dp[j] \cdot (p[i]-p[j])!$ ， $p[i]!$ 为放置前 $p[i]$ 个数不满足第 $i$ 个限制的方案数，对于 $j<i$ ，减去放置前 $p[i]$ 个数满足前 $j-1$ 个限制不满足第 $j$ 个限制的所有方案数 $dp[j]\cdot (p[i]-p[j])!$ ， $(p[i]-p[j])!$ 表示从 $p[j]$ 到 $p[i]$ 的位置可以随意放，这样就可以不重复的计算出 $dp[i]$ ，在最后加一个 $p[i]=n$ 的限制，最后输出 $dp[m]$ 即可。

复杂度为 $O(m^2)$ 。

Code1

#include <bits/stdc++.h>
using namespace std;
const int N=2e3+10;
const int mod=20000311;
typedef long long ll;
ll dp[N][N],f[N];
int n,m,p[N];
int main()
{
    scanf("%d%d",&n,&m);
    dp[0][0]=1;
    for(int i=1;i<=m;i++){
        int x;
        scanf("%d",&x);
        p[x]=1;
    }
    for(int i=1;i<=n;i++){
        memset(f,0,sizeof f);
        f[i-1]=dp[i-1][i-1];
        for(int j=i;j<=n;j++) f[j]=(f[j-1]+dp[i-1][j])%mod;
        for(int j=i;j<=n;j++){
            if(i==j&&p[j]) continue;
            (dp[i][j]+=f[j-1]%mod)%=mod;
            (dp[i][j]+=dp[i-1][j]*(j-i+1)%mod)%=mod;
        }
    }
    printf("%lld\n",dp[n][n]);
    return 0;
}

Code2

#include<bits/stdc++.h>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define per(i,n,x) for(int i=n;i>=x;i--)
#define ll long long
using namespace std;
const int mod=20000311;
const int N=1e5+10;
int n,m;
int p[N],f[N],dp[N];
int main(){
    scanf("%d%d",&n,&m);
    rep(i,1,m){
        scanf("%d",&p[i]);
    }
    f[0]=1;
    rep(i,1,n) f[i]=1ll*f[i-1]*i%mod;
    p[++m]=n;
    sort(p+1,p+m+1);
    for(int i=1;i<=m;i++){
        dp[i]=f[p[i]];
        for(int j=1;j<i;j++) dp[i]=(dp[i]+mod-1ll*dp[j]*f[p[i]-p[j]]%mod)%mod;
    }
    printf("%d\n",dp[m]);
    return 0;
}