2018 Benelux Algorithm Programming Contest (BAPC 18) E.Entirely Unsorted Sequences(计数dp)

题目

思路来源

https://www.cnblogs.com/MXang/p/10182791.html

题解

看人家口胡看不懂，看代码就看懂了

dp[i]表示前i的至少一个有序的方案数，即不合法

ans[i]表示前i的均无序的方案数，即合法

c[l][r]表示[l,r]可重集全排列方案数 ，预处理一下

转移的时候，考虑枚举第一个不合法(即有序)的位置即可

dp总是这样的自己苦想想不出来一看题解恍然大悟

还是要多想想怎么设计状态啊

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<map> 
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=5e3+10,mod=1e9+9;
int n,a[N],x[N],m,num[N];
int dp[N],ans[N],inv[N];//dp[i]表示前i的至少一个有序的方案数 ans[i]表示前i的均无序的方案数 
int c[N][N];//c[l][r]:表示[l,r]可重集全排列方案数 
int main(){ inv[1]=1;for(int i=2;i<N;++i){inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;}scanf("%d",&n);for(int i=1;i<=n;++i){scanf("%d",&a[i]);x[++m]=a[i];}sort(x+1,x+m+1);m=unique(x+1,x+m+1)-(x+1);sort(a+1,a+n+1);for(int i=1;i<=n;++i){a[i]=lower_bound(x+1,x+m+1,a[i])-x;}for(int l=1;l<=n;++l){c[l][l-1]=1;memset(num,0,sizeof num); for(int r=l;r<=n;++r){num[a[r]]++;c[l][r]=1ll*c[l][r-1]*(r-l+1)%mod*inv[num[a[r]]]%mod;}c[l+1][l]=1;}ans[0]=1;for(int i=1;i<=n;++i){//枚举有序的首位置j 统计至少一个不合法的方案数 for(int j=1;j<=i;++j){dp[i]=(dp[i]+1ll*ans[j-1]*c[j+1][i]%mod)%mod;}ans[i]=(c[1][i]-dp[i]+mod)%mod;}printf("%d\n",ans[n]);return 0;
}