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

首先我们要明白dp[i]表示的是什么，看了好久的别人的代码才看懂了(i am vegetable),dp[i]表示的是长度为p[i]，满足前i-1个限制条件的合法子串的个数！（看不懂就看例子）
举个例子，此时的限制条件有3个，分别是p[1]=3,p[2]=5,p[3]=7,那么dp[1]就是表示满足前0个限制条件长度为p[1]=3的合法子串的个数，很明显前0个是没有的，那么dp[1]=3!-0,dp[2]就是表示满足前1个限制条件长度为p[2]=5的合法子串的长度，dp[2]=5!-(不合法长度)，那么不合法长度是多少？仔细看下题目：
第i个限制条件pi表示前pi个数不能是1-pi的排列的排列
dp[1]就是1-3的排列，那么它对于dp[2]来说肯定是不合法的，那有多少种，dp[2]=5,那么第4、5个位置肯定有2！种排列，就是4、5或者5、4，那么dp[2]=5!-dp[1]乘以2!
dp[3]类推，dp[3]=7!-（不合法长度）,不合法长度等于什么呢？很明显，dp[1]表示1-3的排列，此时这个条件对于dp[3]是不合法的，因为dp[3]要满足前i-1个条件（3-1=2）的限制，那么排列有dp[1]乘以(7-3)!，而dp[2]表示的是满足第一个条件的长度为5的合法子串个数，很明显，dp[3]要满足第二个限制条件，dp[2]的排列对于dp[3]来说同样是不合法的，那无法就是dp[2](7-5)!，合起来就是dp[3]=5!-dp[1]2!-dp[2]*2!

#include<iostream>
#include<cstdio>
#include<algorithm>
#define mod 20000311
typedef long long ll;
using namespace std;
ll p[2010];//限制条件
ll dp[2010];//表示在长度为p[i]的串满足前i-1个限制条件的合法长度
ll f[2010];
int main (){
    //初始化，阶乘
    f[0]=1;
    for(int i=1;i<=2000;i++){
        f[i]=(f[i-1]*ll(i))%mod;
    }
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>p[i];
    }
    sort(p+1,p+m+1);
    m++;
    p[m]=n;
    for(int i=1;i<=m;i++){
        dp[i]=f[p[i]];//总排列数
        for(int j=1;j<i;j++){
            dp[i]=(dp[i]-(dp[j]*f[(p[i]-p[j])])%mod+mod)%mod;
        }
    }
    cout<<dp[m]<<endl;
}