数学考试(两种dp方式+容斥思想)

牛客练习赛71 数学考试(两种dp方式+容斥思想)

这道题可以说是对的考察非常特别

好题,但是我是废物,一种做法都没想到

转移是

这部分表示若前个数字不大于,现在就可以放数字来转移

这部分表示若前个数的最大值是,说明还有个小于的没用过

这样最后就是答案

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2009;
const int mod=20000311;
int p[maxn],dp[maxn][maxn],pre[maxn];
signed main()
{
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=m;i++)    cin >> p[i];
    memset(dp,-1,sizeof(dp));
    for(int i=1;i<=n;i++)    dp[1][i]=1;
    for(int i=1;i<=m;i++)    dp[p[i]][p[i]]=0;
    for(int i=1;i<=n;i++)    pre[i]=pre[i-1]+dp[1][i];
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if( dp[i][j]==0 )    continue;
            if( i>j )    dp[i][j]=0;
            else
                dp[i][j] = ( dp[i-1][j]*(j-i+1)+pre[j-1] )%mod;
        }
        for(int j=1;j<=n;j++)
            pre[j] = (pre[j-1]+dp[i][j] )%mod;
    }
    printf("%lld",dp[n][n]);
} 

定义是处理到第个数,前个限制满足条件,第个限制条件不满足

这样就可以做到不重不漏

最后用就是答案

很明显,就是的全排列

那么对吗?算多了,需要减掉在第一个限制条件就不满足的情况

就是$$

意思是的数字仍然在位置,余下来的位置随便排列

接下来就是一样的道理了

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2009;
const int mod=20000311;
int dp[maxn],p[maxn],fac[maxn];
signed main()
{
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=m;i++)    cin >> p[i];
    fac[0]=1;
    for(int i=1;i<=n;i++)    fac[i]=fac[i-1]*i%mod;
    sort(p+1,p+1+m);
    dp[1]=fac[p[1]];
    for(int i=2;i<=m;i++)
    {
        dp[i]=fac[p[i]];
        for(int j=1;j<i;j++)
            dp[i] = ( dp[i]-dp[j]*fac[p[i]-p[j]] )%mod;
    }
    int ans=fac[n];
    for(int i=1;i<=m;i++)    ans = ( ans-dp[i]*fac[n-p[i]] )%mod;
    cout << ( ans%mod+mod )%mod;
}