今天没听懂 h10 的讲课 但已经没有什么好害怕的了
题意
给你两个序列 \(a,b\) 每个序列共 \(n\) 个数 , 数之间两两不同
问 \(a\) 与 \(b\) 之间有多少配对方案 使得 \(a_i>b_i\) 的对数 比 \(b_i > a_i\) 的恰好多 \(k\) 对.
\((1 \le k \le n \le 2000)\)
题解
首先这个对数多的有点恶心 , 我们直接转化成 \(a_i > b_i\) 的共有 \(\frac{n+k}{2}\) 对 (自行模拟一下...)
然后不是整数的时候答案就是 \(0\) ... 这个我没有判断 , 但过了...
然后我们还是用 \(k\) 表示 \(a_i>b_i\) 的对数 .
看到 恰好 我们不难想到 至少 . 我们考虑如何计算至少 \(k\) 对的贡献 .
因为这有一个鬼畜的定理...
广义容斥定理 (二项式反演?) :
\[\displaystyle b_k = \sum_{i=k}^n \binom i k a_i
\]\[\Updownarrow
\]\[\displaystyle a_k = \sum_{i=k}^{n} (-1)^{i-k} \binom i k b_i
\]
这个 h10 讲了证明... 感性理解然后记忆一下吧...
不难想到一个简单的 \(dp\) 我们令 \(dp[i][j]\) 为 \(a\) 中前 \(i\) 个数能选出比 \(b\) 大共有 \(j\) 对的方案数.
然后我们记 \(\displaystyle \sum_{j=1}^n [a_i>b_j] = t_i\) . 也就是 \(a_i\) 比 多少个 \(b_j\) 大
\]
\(dp[i-1][j]\) 就是上一个同样 \(j\) 对时候 此时可以直接转移
\(dp[i-1][j-1]\times (t_i-j+1)\) 这个就是你当前已选了 \(j-1\) 对 , 当前还剩下 \(t_i-j+1\) 个可选
可以这样理解 前者是当前不选时候的贡献 后者是选择时候的贡献
然后此处我们不难发现 \(a\) 必须都要是有序的 不然会算错
DOFY : 排序是为了方便计数....不然你计不了答案...
就是你之前选的方案的 \(t_i\) 应该被后面给包括了 就是后面选方案的时候要算上当前的方案
然后我们令 \(F_i\) 为至少有 \(i\) 对满足 \(a > b\) 的方案数.
\]
然后令恰好有 \(k\) 对满足的 \(G_k\) 就是
\]
然后代码就比较好写咯...
代码
/**************************************************************
Problem: 3622
User: zjp_shadow
Language: C++
Result: Accepted
Time:2184 ms
Memory:64488 kb
****************************************************************/
#include <bits/stdc++.h>
#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
inline bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}
inline bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}
inline int read() {
int x = 0, fh = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -1;
for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);
return x * fh;
}
void File() {
#ifdef zjp_shadow
freopen ("3622.in", "r", stdin);
freopen ("3622.out", "w", stdout);
#endif
}
typedef long long ll;
const int N = 2010;
const ll Mod = 1e9 + 9;
int n, k, a[N], b[N], t[N];
inline void Add(ll &a, ll b) { if ((a += b) >= Mod) a -= Mod; }
ll dp[N][N], F[N], G[N], fac[N], C[N][N];
void Init(int maxn) {
fac[0] = 1;
For (i, 1, maxn)
fac[i] = fac[i - 1] * i % Mod;
C[0][0] = 1;
For (i, 1, maxn) {
C[i][0] = 1;
For (j, 1, maxn)
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % Mod;
}
}
int main () {
File(); Init(2000);
n = read(); k = read();
k = (n + k) >> 1;
For (i, 1, n) a[i] = read();
For (i, 1, n) b[i] = read();
sort(a + 1, a + 1 + n);
dp[0][0] = 1;
For (i, 1, n) {
For (j, 1, n)
if (a[i] > b[j]) ++ t[i];
For (j, 0, n) {
Add(dp[i][j], dp[i - 1][j]);
if (!j) continue ;
Add(dp[i][j], dp[i - 1][j - 1] * max(0, (t[i] - j + 1)) % Mod);
}
}
For (i, 1, n)
F[i] = dp[n][i] * fac[n - i] % Mod;
For (i, k, n) {
G[k] += ((i - k) & 1 ? -1 : 1) * (C[i][k] * F[i] % Mod);
G[k] = (G[k] % Mod + Mod) % Mod;
}
printf ("%lld\n", G[k]);
return 0;
}