[BZOJ 4361] isn（容斥/DP）

Problem

题目地址

Solution

对于一个长度为 (i) 的上升子序列，操作方案数有 ((n-i)!) 种。

令 (g[i]) 表示长度为 (i) 的上升子序列的集合，(g[i]) 仅记录集合元素个数。考虑 (g[i]) 这个集合带来的合法操作方案总数。

全集：对于每一个 (x in g[i])，操作方案数是 ((n-i)!)，故集合 (g[i]) 带来的操作方案总数为 (g[i]*(n-i)!)。（包含不合法方案）

不合法方案数：由 (y in g[i+1])，(y) 中任选一个元素删去，得到的 (y' in g[i]) （(y') 一定属于 (g[i])）即为不合法的操作方案（在上一个操作已经是上升子序列）。不合法的方案数为 (g[i+1]*(n-i-1)*(i+1))

综上，(g[i]) 这个集合带来的合法操作方案总数为：

[g[i]*(n-i)! - g[i+1]*(n-i-1)*(i+1) ]

(g[i]) 可以用树状数组加DP算出，复杂度 (O(n^2 log n))。时间复杂度 (O(n^2 log n))。

Code

Talk is cheap.Show me the code.

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
const int N = 2007, mod = 1e9+7;
int n;
int a[N],g[N],btmp[N],jc[N];
struct BIT {
	int c[N];
	inline void Add(int x,int y) {
		while(x <= n) {
			c[x] = (c[x] + y) % mod; x += x & -x;
		}
	}
	inline int Ask(int x) {
		int res = 0;
		while(x > 0) {
			res = (res + c[x]) % mod; x -= x & -x;
		}
		return res;
	}
}T[N];
signed main()
{
	n = read();
	for(int i=1;i<=n;++i) a[i] = btmp[i] = read();
	sort(btmp+1, btmp+1+n);
	int ntmp = unique(btmp+1, btmp+1+n) - btmp - 1;
	for(int i=1;i<=n;++i) a[i] = lower_bound(btmp+1, btmp+1+ntmp, a[i]) - btmp;
	for(int i=1;i<=n;++i) {
		for(int j=n;j>=2;--j) {
			int res = T[j-1].Ask(a[i]);
			g[j] = (g[j] + res) % mod;
			T[j].Add(a[i],res);
		}
		++g[1]; T[1].Add(a[i],1);
	}
	jc[0] = 1;
	for(int i=1;i<=n;++i) jc[i] = (jc[i-1] * i) % mod;
	int ans = 0;
	for(int i=1;i<=n;++i) {
		ans = (ans + g[i]*jc[n-i]%mod - g[i+1]*jc[n-i-1]%mod*(i+1)%mod + mod) % mod;
	}
	printf("%lld
",ans);
	return 0;
}
/*
4
1 7 5 3

18
*/

Summary

还是减法原理。