[BZOJ3622] 더 이상 무서울 게 없어요. [카운트DP] [포즈]

[제목 링크]
[dyllala의 문제풀이!]
개인적인 이해를 말씀드리자면...
먼저 두 개의 그룹을 정렬하고next[i]를 설정하면 i번째 사탕>j번째 알약을 만족시키는 가장 큰 j를 나타낸다.분명히 이next는 단조로워서 O(n)로 구할 수 있다.
dp[i][j]를 설정하면 전 i개의 사탕에 적어도 j조의 사탕>알약(즉 이 j조 이외의 다른 상황은 고려하지 않음)이 있는 방안수를 나타낸다.i번째 사탕을 고려하면 두 가지 이동이 있다.
(1) 몰라, dp[i][j] = dp[i-1][j]
(2) 한 조의 관계를 구성하고 dp[i][j]=dp[i-1][j-1]*(next[i]-j+1)
그리고 우리는 dp[i][j]를 구했다.
지금 중복되는 상황을 고려하고 있다. 우리는 적어도 적당한 것을 구해야 한다.
f[j]를 설정하면 n개의 사탕 안에 마침 j조의 사탕>알약(분명히 다른 조는 알약>사탕)의 방안 수가 있음을 나타낸다.그렇게 많아
f[j] = dp[n][j] * (n - j)! - ∑(f[i] * C(i, j)),j + 1 <= i <= n
앞의 항목은 뒤의 n-j조의 총 방안이고, 뒤의 항목은 각각'적어도'더 많은 항목을 빼는 것이다.
원신의 세 문제를 드디어 풀었습니다.

/* Pigonometry */
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long LL;

const int maxn = 2005, p = 1000000009;

int n, k, A[maxn], B[maxn], next[maxn];
LL C[maxn][maxn], fact[maxn], dp[maxn][maxn];

inline int iread() {
	int f = 1, x = 0; char ch = getchar();
	for(; ch < '0' || ch > '9'; ch = getchar()) f = ch == '-' ? -1 : 1;
	for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
	return f * x;
}

int main() {
	n = iread(); k = iread();
	if((n - k) & 1) {
		printf("0
");
		return 0;
	}
	k = (n + k) >> 1;

	fact[0] = 1;
	for(int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % p;
	for(int i = 0; i <= n; i++) {
		C[i][0] = 1;
		for(int j = 1; j <= i; j++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % p;
	}

	for(int i = 1; i <= n; i++) A[i] = iread();
	for(int i = 1; i <= n; i++) B[i] = iread();
	sort(A + 1, A + 1 + n); sort(B + 1, B + 1 + n);

	for(int i = 1, j = 0; i <= n; next[i++] = j)
		for(; j < n && A[i] > B[j + 1]; j++);

	dp[0][0] = 1;
	for(int i = 1; i <= n; i++) {
		dp[i][0] = 1;
		for(int j = 1; j <= i; j++)
			dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1] * (next[i] - j + 1) % p) % p;
	}

	for(int i = n; i >= k; i--) {
		dp[n][i] = dp[n][i] * fact[n - i] % p;
		for(int j = i + 1; j <= n; j++)
			dp[n][i] = (dp[n][i] - dp[n][j] * C[j][i] % p + p) % p;
	}

	printf("%lld
", dp[n][k]);
	return 0;
}