题目大意
给定两个长为 n 的序列 a 和 b(2n 个数互不相同),求有多少种匹配方案满足 ai>bi 的组数比 ai<bi 的组数多 k 个。
1⩽n⩽2,000
题目链接
已经没有什么好害怕的了 - Luogu 4859
题解
补完魔圆后再看一遍这道题。。。
首先,n 为奇数时答案为 0。
对两个序列排序,定义 next[i] 表示最大的满足 ai>bj 的 j,考虑 DP,设 f[i,j] 表示已经考虑了 a 中前 i 个数,找到 j 个 b 中的数使得这些数均比 a 中的 i 个数小的方案数(其余不管),则转移为:
f[i,j]=f[i−1,j]+f[i−1,j−1]×(next[i]−(j−1))f[i,0]=1(i=1,2,3…,n)
当然,这不是最终答案,因为在计算 f 时,剩下的是不管的,所以会重算,我们在减去即可。记 g[n,i] 表示 b 中正好有 i 个数比对应的 a 的值小的匹配数,有:
g[n,i]=f[n,i]×(n−i)!−j=i+1∑ng[n,j]∗(ij)
计算时,对于每一个 j,我们减去有 j 个数小的答案却被记入 i 个数中的个数,也就是在正好 j 个数中选 i 个继续匹配的个数。
代码
由于我们只需计算 g[n,i],故数组 g 只需一维。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
| #include <cstdio> #include <algorithm>
const int MAXN = 2005; const int MOD = 1e9 + 9; int a[MAXN], b[MAXN], next[MAXN]; long long fac[MAXN], combin[MAXN][MAXN]; void calc(int n) { fac[0] = 1; for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % MOD; for (int i = 0; i <= n; i++) { combin[i][0] = 1; for (int j = 1; j <= i; j++) combin[i][j] = (combin[i - 1][j] + combin[i - 1][j - 1]) % MOD; } } long long f[MAXN][MAXN]; void dp(int n) { f[0][0] = 1; for (int i = 1; i <= n; i++) { f[i][0] = 1; for (int j = 1; j <= i; j++) f[i][j] = (f[i - 1][j] + f[i - 1][j - 1] * std::max(next[i] - j + 1, 0)) % MOD; } } int main() { int n, k; scanf("%d %d", &n, &k); if ((n + k) & 1) { puts("0"); return 0; } int s = (n + k) >> 1; for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = 1; i <= n; i++) scanf("%d", &b[i]); std::sort(a + 1, a + n + 1); std::sort(b + 1, b + n + 1); for (int i = 1, j = 1; i <= n; i++) { while (j <= n && a[i] > b[j]) j++; next[i] = j - 1; } #ifdef DBG puts("next :"); for (int i = 1; i <= n; i++) printf(" %d", next[i]); puts(""); #endif dp(n); #ifdef DBG puts("dp - f :"); for (int i = 0; i <= n; i++) { for (int j = 0; j <= i; j++) printf("f[%d][%d] = %lld ", i, j, f[i][j]); puts(""); } #endif calc(n); static long long g[MAXN]; for (int i = n; i >= s; i--) { g[i] = f[n][i] * fac[n - i] % MOD; for (int j = i + 1; j <= n; j++) g[i] = (g[i] + MOD - g[j] * combin[j][i] % MOD) % MOD; #ifdef DBG printf("g[%d] = %lld\n", i, g[i]); #endif } printf("%lld\n", g[s]); return 0; }
|