【BZOJ 4361】isn

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4361
数据传送门:http://oi.cyo.ng/?attachment_id=1898

题解

考虑一个长度为i的非下降子序列
如果忽略成为非下降子序列就停止的限制
那么其对于答案的贡献为g[i]*(n-i)!

现在考虑成为非下降子序列就停止的限制
对于长度为i的非下降子序列,非法的话,一定是从i+1的序列删掉一个数
所以减掉\(g[i + 1] \cdot (n – (i + 1))! \cdot (i + 1)\)即可

至于为什么这样会不重不漏、刚好删掉所有非法方案?
唯一的疑惑就在于有一些方案不在第一次非法时删除
但不难发现将第一段+第二段看成一个操作的话
每一个操作刚好不重不漏加上了所有的合法方案

代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 2000+9;
const int MOD = 1000000007;

int tot,n,_hash[N],arr[N],f[N],POW[N]; 

namespace Fenwick_Tree{
	#define BIT Fenwick_Tree
	#define lowbit(x) ((x)&-(x))
	int cnt[N][N];
	
	inline void insert(int t, int p, int delta) {
		for (int i=p;i<=n;i+=lowbit(i)) 
			(cnt[t][i] += delta) %= MOD;
	}
	
	inline int query(int t, int p) {
		int ret = 0;
		for (int i=p;i;i-=lowbit(i))
			(ret += cnt[t][i]) %= MOD;
		return ret;
	} 
};

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int main(){
	n = read();
	for (int i=1;i<=n;i++) 
		_hash[i] = arr[i] = read();
	sort(_hash+1, _hash+1+n);
	tot = unique(_hash+1, _hash+1+n) - _hash - 1;
	for (int i=1;i<=n;i++) 
		arr[i] = lower_bound(_hash+1, _hash+1+tot, arr[i]) - _hash;
	POW[1] = POW[0] = 1;
	for (int i=2;i<=n;i++) 
		POW[i] = (LL)POW[i-1] * i % MOD;
	
	for (int i=1;i<=n;i++) {
		for (int j=n,tmp;j>1;j--) {
			tmp = BIT::query(j-1,arr[i]);
			(f[j] += tmp) %= MOD;
			BIT::insert(j,arr[i],tmp);
		}
		BIT::insert(1,arr[i],1);
		f[1]++;
	} 
	
	int vout = 0;
	for (int i=1;i<=n;i++) {
		(vout += (LL)f[i] * POW[n-i] % MOD) %= MOD;
		if (i < n) 
			(vout -= ((LL)f[i+1] * POW[n-i-1] % MOD) * (i+1) % MOD) %= MOD;
	}
	printf("%d\n",(vout+MOD)%MOD);
	return 0;
}