「BZOJ 4361」isn 題解

知識點

DP，組合數學，容斥，樹狀數組。

分析

首先，我們不考慮「非降時停止」這個限制，那么則可用 DP 求解。

設 \(f_{i,j}\) 表示 \(1\sim i\) 中，組成一個長度為 \(j\) 的非降子序列的方案數。初態和轉移式：

這個問題答案就是：

然后我們來考慮「非降時停止」：其實只要把每個不合法的從原本的減掉即可，而這些不合法的我們都可以從已有的 DP 狀態中推出來。

我們簡化一下，設 \(g_i\) 表示所有組成長度為 \(i\) 的非降子序列的方案數，即：

那么考慮「非降時停止」的組成長度為 \(i\) 的非降子序列方案數就是：\((n-i)!\cdot g_i - (i+1)(n-i-1)!\cdot g_{i+1}\)。所以累加即可。

DP 暴力可做到 \(O(n^3)\)，離散化后用樹狀數組即可優化到 \(O(n^2\log_2{n})\)。

代碼

//#define Plus_Cat ""
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define RCL(a,b,c,d) memset(a,b,sizeof(c)*(d))
#define FOR(i,a,b) for(int i(a);i<=(int)(b);++i)
#define DOR(i,a,b) for(int i(a);i>=(int)(b);--i)
#define tomax(a,...) ((a)=max({(a),__VA_ARGS__}))
#define tomin(a,...) ((a)=min({(a),__VA_ARGS__}))
#define EDGE(g,i,x,y) for(int i=(g).h[(x)],y=(g)[(i)].v;~i;y=(g)[(i=(g)[i].nxt)>0?i:0].v)
#define main Main();signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);return Main();}signed Main
using namespace std;
constexpr int N(2e3+10);

namespace Modular {
#define Mod 1000000007
	int fac[N];
    //Modular
	void Init(const int n=N-5) {
		FOR(i,fac[0]=1,n)fac[i]=mul(fac[i-1],i);
	}
} using namespace Modular;

int n,ans;
int a[N],b[N],f[N];

class BIT {
private:
	int c[N];
public:
	void Init() { RCL(c+1,0,int,b[0]); }
#define lowbit(i) ((i)&-(i))
	void Plus(int x,int d) { if(x>0)for(; x<=b[0]; x+=lowbit(x))toadd(c[x],d); }
#undef lowbit
	int Sum(int x) {
		int ans(0);
		if(x>0)for(; x; x&=x-1)toadd(ans,c[x]);
		return ans;
	}
} bit;

signed main() {
#ifdef Plus_Cat
	freopen(Plus_Cat ".in","r",stdin),freopen(Plus_Cat ".out","w",stdout);
#endif
	cin>>n,Init(n),ans=mul(n,fac[n-1]);
	FOR(i,1,n)cin>>a[i],b[i]=a[i],f[i]=1;
	sort(b+1,b+n+1),b[0]=unique(b+1,b+n+1)-b-1;
	FOR(i,1,n)a[i]=lower_bound(b+1,b+b[0]+1,a[i])-b;
	FOR(len,2,n) {
		bit.Init(),bit.Plus(a[len-1],f[len-1]),f[len-1]=0;
		int sum(0);
		FOR(i,len,n) {
			int tmp(bit.Sum(a[i]));
			bit.Plus(a[i],f[i]),toadd(sum,f[i]=tmp);
		}
		toadd(ans,Mod-mul(sum,len-1,fac[n-len]));
	}
	cout<<ans<<endl;
	return 0;
}