Lflame

【2016/4/28 考题】isn 递推 巧妙计算不合法方案

    题意:给出一个长度为 n 的序列 A。如果序列 A 不是非降的,你必须从中删去一个数,重复这一操作,直到 A 非降为止。求有多少种不同的操作方案,答案模 10^9+7。 ( n<=2000 )


    令 f[i] 表示长度为 i 的非降子序列个数。那么对于一个长度 i,最后只剩长度为 i 的序列的总方案数为 f[i]*(n-i)!,即选的 n-i 个数可以任意互换顺序。

    但是总方案中会包含不合法的方案,我们来考虑减去它。不合法意味着在长度减到 i 之前,剩下的序列就已经非降了,这时,接下来无论删去什么,这个序列总是保持非降的。

    这也就是说,长度减到 i+1 之前就不合法的方案,长度减到 i+1 时一定是非降的,而最后选的显然是这 i+1 个位置中的一个 ;长度减到 i+1 时才不合法的方案,显然也满足这长度为 i+1 的序列是非降的,最后选的同样是这 i+1 个位置中的一个。所以一个不合法的方案一定会使得其长度减到 i+1 时是非降的,而长度减到 i+1 时若序列非降则这个方案一定不合法,恰好一一对应。

    于是不合法的方案数为 f[i+1]*(n-i-1)!*(i+1)。

    答案即为 sigma{ f[i]*(n-i)! - f[i+1]*(n-i-1)!*(i+1) , 1<=i<=n}。


    而f[i]的求法就很简单了,用一个 dp[i][j] 表示以下标为 i 的数结尾,长度为 j 的非降子序列个数, dp[i][j]从dp[k][j-1]转移过来,其中 k<i 且 A[k]<=A[i],用一个树状数组优化转移即可。


    

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define lowbit(x) ((x)&(-(x)))

using namespace std;


const int MOD=1000000007 , INF=(1<<30)-1;

int n , A[2005] , dp[2005][2005] , f[2005] , B[2005] , bnum ;

long long jc[2005] ;

//dp[i][j] 表示以第 i 个结尾,长度为 j 的非降子序列个数

//f[i] 表示长度为 i 的非降子序列个数


inline void update(int &a,const long long &b,const int &M=MOD){

a+=(int)b ;

if(a>=M)a-=M ;

if(a<0)a+=M ;

}


int H_MOD=1000007 , fha[1000055] , xh[1000055] ;

int H(int a){

int t=((a>>3)+(a>>8)+a)%H_MOD ;

while(fha[t]!=-INF && fha[t]!=a) update(t,107,H_MOD) ;

if(fha[t]==-INF)fha[t]=a ;

return t;

}


struct Fenwick_Tree{

int Fen[2005] ;

int query(int pos){

int ret=0 ;

while(pos)update(ret,Fen[pos]) , pos-=lowbit(pos) ;

return ret;

}


void add(int pos,int num){ while(pos<=n)update(Fen[pos],num) , pos+=lowbit(pos) ; }

}FT[2005];


void solve(){

FT[0].add(1,1) ;

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

int tha=H(A[i]) ;

for(int j=1;j<=i;++j) dp[i][j]=FT[j-1].query(xh[tha]) ;

for(int j=1;j<=i;++j) FT[j].add(xh[tha],dp[i][j]) ;

}

for(int i=1;i<=n;++i) for(int j=1;j<=i;++j)update(f[j],dp[i][j]) ;

int ans=0 ;

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

update(ans,jc[n-i]*f[i]%MOD) ;

if(i!=n)update(ans,-jc[n-i-1]*f[i+1]%MOD*(i+1)%MOD) ;

}

printf("%d\n",ans) ;

}


int main()

{

freopen("isn.in","r",stdin) ;

freopen("isn.out","w",stdout) ;

scanf("%d",&n) ;

jc[0]=1 ;

for(int i=0;i<=1000015;++i)fha[i]=-INF ;

for(int i=1;i<=n;++i)scanf("%d",&A[i]) , jc[i]=jc[i-1]*i%MOD , B[i]=A[i] ;

bnum=n ;

sort(B+1,B+bnum+1) ;

bnum=unique(B+1,B+bnum+1)-B-1 ;

for(int i=1;i<=bnum;++i){ int tha=H(B[i]) ; xh[tha]=i ; }

solve() ;

return 0;

}

评论

热度(3)