bzoj4361isn dp+容斥

2022-07-13 07:26:19

4361: isn

Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 370 Solved: 182
[Submit][Status][Discuss]

Description

给出一个长度为n的序列A(A1,A2...AN)。如果序列A不是非降的，你必须从中删去一个数，

这一操作，直到A非降为止。求有多少种不同的操作方案，答案模10^9+7。

Input

第一行一个整数n。

接下来一行n个整数，描述A。

Output

一行一个整数，描述答案。

Sample Input

4
1 7 5 3

Sample Output

HINT

1<=N<=2000

先找出长度为i的非降序列方案数,再对于每个方案在原序列中删除其它元素可得答案
f[i][j]表示长度为i,以第j个元素结尾构成非降序列方案数
转移n^3 bit优化至n^2*log2(n)
g[i]表示长度为i的非降序列个数,可以对f[][]求和得到

接下来考虑每个方案,在原序列中删除一些数来得到答案

对于长度为i的非降序列,可以在原串中删去剩余的n-i个元素来得到
由于删除是有顺序的,所以删除方案是 (n-i)!
那么对于每个i,它贡献的答案就是g[i]*(n-i)!
但是,由于有些删除方法到长度i+1时就已经非降,所以 -(n-i-1)!*(i+1)*g[i+1]
*(i+1)是因为还要选择一个删去才得到长度i的序列
那么ans=sum(g[i]*(n-i)!-(n-i-1)!*(i+1)*g[i+1])

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#define ll long long

#define mod 1000000007

#define N 2005

using namespace std;

int a[N],b[N],fac[N],n;ll f[N][N],c[N],g[N];

void plu(ll &x,ll y){

    x+=y;x>mod?x-=mod:1;

}

void update(int p,int val){

    while(p<=n){

        plu(c[p],val);

        p+=p&-p;

    }

}

ll sum(int p){

    ll t=0;

    while(p){

        plu(t,c[p]);

        p-=p&-p;

    }

    return t;

}

int main(){

    scanf("%d",&n);

    for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];

    sort(b+1,b+1+n);

    int len=unique(b+1,b+1+n)-b-1;

    for(int i=1;i<=n;i++)

    a[i]=lower_bound(b+1,b+1+len,a[i])-b;

    for(int i=1;i<=n;i++)f[1][i]=1;

    for(int i=2;i<=n;i++){

        memset(c,0,sizeof(c));

        for(int j=1;j<=n;j++){

            plu(f[i][j],sum(a[j]));

            update(a[j],f[i-1][j]);

        }

    }

    for(int i=1;i<=n;i++)

    for(int j=1;j<=n;j++)

    plu(g[i],f[i][j]);

    ll ans=0;

    fac[0]=1;

    for(int i=1;i<=n;i++)fac[i]=(1ll*fac[i-1]*i)%mod;

    for(int i=n;i;i--)

    ans=(ans+(g[i]*fac[n-i])%mod-((g[i+1]*(i+1))%mod*fac[n-i-1])%mod)%mod;

    ans<0?ans+=mod:1;

    cout<<ans;

    return 0;

}

码农公寓