祎隋

强军战歌
Description给出一个数列取模。我们定义删除方案不同有两种情况:删掉的数构成的集合不同删掉的数构成的集合相...
扫描右侧二维码阅读全文
15
2019/02

强军战歌

Description

给出一个数列$$A$$,当这个数列不是不下降的时候我们删除其中一个数,直到它是不下降的。求不同的删除方案总数,答案对$$1000000007$$取模。我们定义删除方案不同有两种情况:

  • 删掉的数构成的集合不同
  • 删掉的数构成的集合相同,但删除顺序不同

Sample Input

3
1 7 5

Sample Output

4

Hint

$1<=n<=2000,1<=A_i<=2000$

Solution

探究问题本质,发现是删掉数后刚好(首次)是个非严格LIS,那么我们如果去掉刚好这个限制,总方案数就会是$\sum_{i=1}^{n} cnt_i \ast (n-i)!$,其中$cnt_i$为长度为i的LIS个数,那么显然这样是不行的,因为有很多不合法的计入了。
那么什么样的是不合法的呢,即已经是LIS之后还继续删除,这样的数即为$\sum_{i=2}^{n} cnt_i \ast i \ast (n-i)!$,注意这里1的没有计入,因为1删完之后就没了a23333.
综上,$ans=\sum_{i=1}^{n} cnt_i \ast (n-i)!-\sum_{i=2}^{n} cnt_i \ast i \ast (n-i)!$.
然后是对于$cnt_i$的计算,我们设dp(i,j)表示以i结尾长度为j的LIS个数,那么:
(tips:可以了解一下这个思路,以后统计找结尾和长度以便于统计,因为LIS结尾要求递增,可以dp)
$dp[i][j]+=dp[k][j-1] k在j前面且a[k]<=a[j]$
由于范围限制,我们使用树状数组来维护将其优化到$n^2logn$,那么这里需要离散化来确定哪些比它小。(详见代码注释)

上代码:

#include<bits/stdc++.h>
#define maxn 2005 
using namespace std;
typedef long long ll;
const ll mod=1000000007;
int n,a[maxn],aa[maxn];
ll dp[maxn][maxn];//以i结尾,长度为j 
ll cnt[maxn];
ll jc[maxn];
ll c[maxn][maxn];//c[i][j]:长度为i,在j前面(lowbit长度)的方案数 
void ready(){
    jc[0]=1;
    for(ll i=1;i<=2000;i++) jc[i]=jc[i-1]*i%mod;
}
void update(int w,int i,ll d){
     while(i<=n){
         c[w][i]=(c[w][i]+d)%mod;
         i+=(i&-i);
     }
}
ll sum(int w,int i){
    ll res=0;
    while(i>0){
        res=(res+c[w][i])%mod;
        i-=(i&-i);
    }
    return res;
}
void init(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    
    /*for(int i=1;i<=n;i++){
       rear=0;
       for(int j=i;j<=n;j++){
           int t=upper_bound(q+1,q+rear+1,a[j])-q;
           if(t==rear+1) q[++rear]=a[j];else{
               if(t==1) continue;//头不能更换 来保证独立性,以当前为开头 
               q[t]=a[j];
        } 
        cnt[t]++;
           for(int k=t-1;k>=2;k--) cnt[k]++; 
       }
    }*///干!不行aaaaaaaaaaaa
    memcpy(aa,a,sizeof(a));
    sort(aa+1,aa+n+1);
    int cntt=unique(aa+1,aa+n+1)-aa-1;
    /*for(int i=1;i<=n;i++){//枚举开头 
        memset(c,0,sizeof(c));
        dp[i][1]=1;
        int pos=lower_bound(aa+1,aa+n+1,a[i])-aa;
        update(1,pos,1); 
        for(int j=2;j<=n;j++){
        ll calc=0;    
        for(int k=i+1;k<=n;k++){
            pos=lower_bound(aa+1,aa+n+1,a[k])-aa;
            int tt=sum(j-1,pos-1);
            calc+=tt;
            update(j,pos,tt);
        }
        dp[i][j]=calc;    
        }
    }*/
    for(int i=1;i<=n;i++){
        dp[i][1]=1; 
        for(int j=2;j<=i;j++){
        int pos=lower_bound(aa+1,aa+cntt+1,a[i])-aa;
        dp[i][j]=sum(j-1,pos);//等于长度为j-1的 
        }
        for(int k=1;k<=i;k++){
        int pos=lower_bound(aa+1,aa+cntt+1,a[i])-aa;
        update(k,pos,dp[i][k]);    
        }  
    }
    
    
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++) cnt[j]=(cnt[j]+dp[i][j])%mod;
    
    ll all=0;
    for(int i=1;i<=n;i++){
        all=(all+cnt[i]*jc[n-i]%mod)%mod;
    }
    ll del=0;
    for(int i=2;i<=n;i++){
        del=(del+cnt[i]*i%mod*jc[n-i]%mod)%mod;
    }
    ll ans=(all-del+mod)%mod;
    printf("%lld",ans);
}
int main(){
    ready();
    init();
    
    return 0;
}
Last modification:February 15th, 2019 at 09:53 pm

Leave a Comment