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

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

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

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

$\color{Red}Ⅰ.考虑到前i个数不能是[1,i]的排列$

$等价于前i个数出现过大于i的数字$

$定义dp[i][j]为前i个数字种最大是j的排列数字$

转移是 $dp[i][j]=dp[i-1][j]*(i-j+1)+pre[j-1]$

$pre[j-1]=\sum\limits_{i=1}^{j-1}dp[i-1][i]$

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

$dp[i-1][j]*(j-i+1)$

这部分表示若前 $i-1$ 个数的最大值是 $j$ ,说明还有 $j-(i-1)$ 个小于 $j$ 的没用过

这样最后 $dp[n][n]$ 就是答案

#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]);
}

$\color{Red}第二种做法是一维的,也很巧妙$

定义 $dp[i]$ 是处理到第 $p[i]$ 个数,前 $i-1$ 个限制满足条件,第 $i$ 个限制条件不满足

这样就可以做到不重不漏

最后用 $n!-\sum\limits_{i=1}^{m}dp[i]$ 就是答案

$dp[1]=fac[p[1]]$ 很明显,就是 $[1,p[1]]$ 的全排列

那么 $dp[2]=fac[p[2]]$ 对吗?算多了,需要减掉在第一个限制条件就不满足的情况

就是$ $dp[2]=fac[p[2]]-dp[1]*fac[p[2]-p[1]]$ $

意思是 $[1,p[1]]$ 的数字仍然在 $[1,p[i]]$ 位置,余下来的位置随便排列

接下来就是一样的道理了

#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;
}