[bzoj4361]isn

DP 容斥 树状数组

题面

给出一个长度为$n$的序列$\{A\}$。如果序列A不是非降的，你必须从中删去一个数。
重复这一操作，直到$\{A\}$非降为止。求有多少种不同的操作方案。

• $n\leq2000$

解析

首先肯定要离散化。（因为只关心相对大小）
于是数字范围为$[1,n]$。

我们需要求得$g[i]$，表示长度为$i$的最长不下降子序列个数。
怎么求？
设$f[i][j]$表示统计第$1～i$个数字，得到最长不下降子序列末端为$j$。
（实际上，只有这样设状态才能转移）
显然这个状态可以从前面所有$f[i'][j'](i'<i\&\&j'<=j)$转移过来。
树状数组优化一下。
注意要防止$dp$统计到自己之前统计的状态。

考虑到在$g[i]$状态下，我们可以以任意顺序删去$n-i$个数，则长度为$i$的最长不下降子序列方案数为$g[i]*(n-i)!$
但是，不能保证它在成为最长不下降子序列时就停止删数。
不合法方案数为$g[i+1]*(n-i-1)!*(i+1)$（最后一次可以删$i+1$个数中任意一个）。
倒着推，每次结果（$g[i]$)都是合法的。
因而只要管第$i+1$个数的情况就够了。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=2005,mod=1e9+7;
ll dp[N][N],n,a[N],t[N],jc[N],o[N],len,f[N],ans;
il void add(re int x,re ll w){for(re int i=x;i<=n;i+=i&-i) (t[i]+=w)%=mod;}
il ll Query(re int x) {re ll res=0;for(re int i=x;i;i-=i&-i) (res+=t[i])%=mod;return res;}
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
int main()
{
  n=gi();
  fp(i,1,n) o[i]=a[i]=gi();o[n+1]=0;
  sort(o+1,o+2+n);len=unique(o+1,o+2+n)-o-1;
  fp(i,0,n) a[i]=lower_bound(o+1,o+1+len,a[i])-o;
  jc[0]=1;fp(i,1,n) jc[i]=(jc[i-1]*i)%mod;
  dp[0][0]=1;
  fp(j,1,n)
  {
    memset(t,0,sizeof(t));
    fp(i,1,n)
    {
      add(a[i-1],dp[i-1][j-1]);
      dp[i][j]=Query(a[i]);
      (f[j]+=dp[i][j])%=mod;
    }
  }
  (ans+=f[n])%=mod;
  fq(i,n-1,1) ans=((ans+f[i]*jc[n-i]%mod-f[i+1]*jc[n-i-1]%mod*(i+1)%mod)+mod)%mod;
  printf("%lld\n",ans);
  return 0;
}