感觉是个好题

Description

link

去链接看吧

Solution

首先定义两个状态：

\(f_{i,j}\) 表示长度为 \(i\) 最后一位在 \(j\) 的不降子序列个数

\(g[i]=\sum\limits_{j=1}^{n} f[i][j]\) ，也就是长度 \(i\) 的不降序列个数

对于如何转移 \(f\) ：

在 \(1 \rightarrow i-1\) 中找小于 \(a_i\) 的数，然后统计答案

\(O(n^3)\) 显然无法接受

我们用树状数组优化这个过程，有点像二维数点

把复杂度降下来到\(O(n^2\log \ n)\)

统计 \(g\) 的答案：

留下长度为 \(i \Leftrightarrow\) 去掉长度为 \(n-i\) 的

有序的计数，应该是 \(ans=\sum\limits_{i=1}^{n} g[i] \times (n-i)!\)

但是我们发现在删掉 \(i-1\) 的时候可能就停下来了

所以我们要容斥这个过程

我们发现在一个 \(i+1\) 的合法序列中删掉任何一个都可以得到合法长度为 \(i\) 的序列

然后就直接\(ans=\sum\limits_{i=1}^{n} g_i \times (n-i)!-(n-i-1)!(i+1)g_{i+1}\)

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace yspm{
	inline int read()
	{
		int res=0,f=1; char k;
		while(!isdigit(k=getchar())) if(k==‘-‘) f=-1;
		while(isdigit(k)) res=res*10+k-‘0‘,k=getchar();
		return res*f;
	}
	const int mod=1e9+7,N=2010;
	int c[N],b[N],a[N],f[N][N],g[N],n,m,ans,fac[N];
	inline int lowbit(int x){return x&(-x);}
	inline void add(int x,int y)
	{
		for(;x<=m;x+=lowbit(x)) c[x]+=y,c[x]%=mod;;
		return ; 
	}
	inline int ask(int x)
	{
		int res=0;
		for(;x;x-=lowbit(x)) res+=c[x],res%=mod;
		return res;
	}
	inline void clear(){for(int i=1;i<=n;++i) c[i]=0; return ;}
	signed main()
	{
		n=read(); for(int i=1;i<=n;++i) b[++m]=a[i]=read();
		fac[0]=1; for(int i=1;i<=n;++i) fac[i]=fac[i-1]*i%mod;
		sort(b+1,b+m+1); m=unique(b+1,b+n+1)-b-1;
		for(int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+m+1,a[i])-b;
		for(int i=1;i<=n;++i) f[1][i]=1;
		for(int i=1;i<=n;++i)
		{
			clear();
			for(int j=1;j<=n;++j)
			{
				f[i][j]+=ask(a[j]); f[i][j]%=mod;
				add(a[j],f[i-1][j]);
			}
		}
		for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) g[i]+=f[i][j],g[i]%=mod;
		for(int i=n;i>=1;--i) 
		{
			ans+=g[i]*fac[n-i]%mod; ans%=mod;
			ans-=g[i+1]*fac[n-i-1]%mod*(i+1)%mod;
			(ans+=mod)%=mod;
		}
		printf("%lld\n",ans);
		return 0;
	}
}
signed main(){return yspm::main();}

BZOJ4361 isn

原文：https://www.cnblogs.com/yspm/p/12790627.html