Description:
有两个数组a和b，两两配对，求 \(a_i>b_i\) 的配对比 \(b_i>a_i\) 的配对多 \(k\) 个的方案数
\(k\le n\le 2000\)
Solution:
先将 \(a，b\) 排序，求出 \(cnt[i]\) 表示比 \(a[i]\) 小的 \(b[j]\) 有多少个，然后恰好k个不好求，求至少 \(k\) 个，然后容斥。
设 \(dp[i][j]\) 表示到 \(a\) 的前 \(i\) 位，有 \(j\) 对 \(a>b\) ：\[ dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] \times(cnt[i] - j + 1) \] 然后随便容斥一下就好了，不要忘了乘组合数。\[ Ans = \sum_{i=k}^n(-1)^{i-k}{~i~ \choose k}dp[n][i](n-i)! \]
Code
#include <vector>
#include <cmath>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <iostream>
#include <algorithm>
typedef long long LL;
typedef unsigned long long uLL;
#define fir first
#define sec second
#define SZ(x) (int)x.size()
#define MP(x, y) std::make_pair(x, y)
#define PB(x) push_back(x)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define GO debug("GO\n")
#define rep(i, a, b) for (register int i = (a), i##end = (b); (i) <= i##end; ++ (i))
#define drep(i, a, b) for (register int i = (a), i##end = (b); (i) >= i##end; -- (i))
#define REP(i, a, b) for (register int i = (a), i##end = (b); (i) < i##end; ++ (i))
inline int read() {
register int x = 0; register int f = 1; register char c;
while (!isdigit(c = getchar())) if (c == '-') f = -1;
while (x = (x << 1) + (x << 3) + (c xor 48), isdigit(c = getchar()));
return x * f;
}
template<class T> inline void write(T x) {
static char stk[30]; static int top = 0;
if (x < 0) { x = -x, putchar('-'); }
while (stk[++top] = x % 10 xor 48, x /= 10, x);
while (putchar(stk[top--]), top);
}
template<typename T> inline bool chkmin(T &a, T b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b, 1 : 0; }
using namespace std;
const int maxN = 2003;
const int MOD = 1e9 + 9;
int n, k, ans;
int C[maxN][maxN], dp[maxN][maxN], a[maxN], b[maxN], cnt[maxN], fac[maxN];
void pls(int &x, int y)
{
x += y;
if (x >= MOD) x -= MOD;
if (x < 0) x += MOD;
}
void init()
{
C[0][0] = 1;
for (int i = 1; i <= n; ++i)
{
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; ++j)
pls(C[i][j], C[i - 1][j]), pls(C[i][j], C[i - 1][j - 1]);
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("xhc.in", "r", stdin);
freopen("xhc.out", "w", stdout);
#endif
cin >> n >> k;
if ((n + k) & 1)
{
puts("0");
return 0;
}
k = (n + k) >> 1;
for (int i = 1; i <= n; ++i)
cin >> a[i];
for (int i = 1; i <= n; ++i)
cin >> b[i];
sort(a + 1, a + 1 + n);
sort(b + 1, b + 1 + n);
init();
fac[0] = 1;
for (int i = 1; i <= n; ++i) fac[i] = 1ll * fac[i - 1] * i % MOD;
for (int i = 1; i <= n; ++i)
{
cnt[i] = cnt[i - 1];
while (a[i] > b[cnt[i]] and cnt[i] <= n)
cnt[i]++;
cnt[i]--;
}
dp[0][0] = 1;
for (int i = 1; i <= n; ++i)
{
for (int j = 0; j <= cnt[i]; ++j)
{
pls(dp[i][j], dp[i - 1][j]);
if (j)
pls(dp[i][j], 1ll * dp[i - 1][j - 1] * max(cnt[i] - j + 1, 0) % MOD);
}
}
for (int i = k; i <= n; ++i)
{
if ((i - k) & 1)
pls(ans, -1ll * dp[n][i] * fac[n - i] % MOD * C[i][k] % MOD);
else
pls(ans, 1ll * dp[n][i] * fac[n - i] % MOD * C[i][k] % MOD);
}
cout << ans << endl;
return 0;
}
转载于:https://www.cnblogs.com/cnyali-Tea/p/11439897.html
相关资源：JAVA上百实例源码以及开源项目
