BZOJ4361 isn

BZOJ

分析

考虑一个长度为$i$的非子序列对答案的贡献是什么。可以发现是$i\times (n-i)!$。

但是这样子会有一些非法情况:在删掉一个数之前序列已经是非降的了。

设$g[i]$表示长度为$i$的非降子序列的个数。

考虑长度为$i$的不下降子序列对答案的贡献。

显然,如果先构成了一个长度为$i+1$的非降子序列,然后再删掉一个数,是不合法的。

所以长度为$i$的非降子序列的贡献为$\large g[i]\times(n-i)!-g[i+1]\times (n-i-1)!\times(i+1)$。

再考虑$g[i]$怎么算。设$f[i][j]$表示以$i$结尾的长度为$j$的非降子序列的个数。

容易得到:$\large f[i][j]=\sum f[k][j-1]\quad(k<i,a[k]\leq a[i])$。

这个东西可以用树状数组优化一下,然后就做到了$O(n^2\,\log\,n)$。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=2000+10;
const int MOD=1e9+7;

int n,tot=0;
int a[MAXN],tmp[MAXN];
int c[MAXN];
int fact[MAXN];
int f[MAXN][MAXN],g[MAXN];

inline void pls(int& x,int y) { x+=y; if (x>=MOD) x-=MOD; }
inline int lowbit(int x) { return x&-x; }
inline void add(int x,int y) { for (;x<=tot;x+=lowbit(x)) pls(c[x],y); }
inline int sum(int x,int ans=0) { for (;x;x-=lowbit(x)) pls(ans,c[x]); return ans; }

int main() {
    n=read();
    for (re int i=1;i<=n;++i) a[i]=read(),tmp[++tot]=a[i];
    sort(tmp+1,tmp+tot+1); tot=unique(tmp+1,tmp+tot+1)-tmp-1;
    for (re int i=0;i<=n;++i)
        a[i]=lower_bound(tmp+1,tmp+tot+1,a[i])-tmp;
    f[0][0]=1;
    for (re int j=1;j<=n;++j) {
        memset(c,0,sizeof(c));
        for (re int i=1;i<=n;++i) {
            add(a[i-1],f[i-1][j-1]);
            f[i][j]=sum(a[i]);
            pls(g[j],f[i][j]);
        }
    }
    fact[0]=1;
    for (re int i=1;i<=n;++i) fact[i]=1ll*fact[i-1]*i%MOD;
    int ans=g[n];
    for (re int i=1;i<n;++i)
        pls(ans,(1ll*g[i]*fact[n-i]%MOD-1ll*g[i+1]*fact[n-i-1]%MOD*(i+1)%MOD+MOD)%MOD);
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 09 月 24 日 09 : 58 PM

发表评论