题目链接
学习链接
设状态 \(dp[i][j]\) 表示整数 \([1,i]\) 满足要求的排列中，最后一个数选 \(j\) 的排列数。
开一个数组记录他的状态：
把前面已选好的序列中大于等于 \(j\) 的数都加一后再把 \(j\) 加到后面。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=1e9+7;
const int N=5e3+10;
int n,a,b,x;int p[N];
int dp[N][N],s[N];int main(){ios::sync_with_stdio(false);cin>>n>>a>>b;for(int i=1;i<=a;i++){cin>>x;++x;p[x]=1;p[x+1]=2;}for(int i=1;i<=b;i++){cin>>x;++x;p[x]=2;p[x+1]=1;}dp[1][1]=s[1]=1;for(int i=2;i<=n;i++){for(int j=1;j<=i;j++){if(p[i]==0){dp[i][j]+=s[i-1];dp[i][j]%=mod;}else if(p[i]==1){dp[i][j]+=(s[i-1]-s[j-1]+mod)%mod;dp[i][j]%=mod;}else{dp[i][j]+=s[j-1];dp[i][j]%=mod;}}for(int j=1;j<=i;j++){s[j]=(s[j-1]+dp[i][j])%mod;}}ll ans=0;for(int i=1;i<=n;i++){ans+=dp[n][i];ans%=mod;}cout<<ans;return 0;
}
