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

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

题意

求 的排列，有 个限制条件，第个限制条件 表示前 个数不能是 的排列，求符合要求的排列的个数。 答案对 20000311 取模。

做法1

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

• ，说明这一位有限制。
• 否则，，表示若，那么第位只能放一种数，若，第位可以放种数，前面的部分可以前缀和优化。

复杂度为。

做法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;
}