洛谷P4859 已经没有什么好害怕的了 题解
题目链接:P4859 已经没有什么好害怕的了
题意:
已经使 Madoka 有签订契约,和自己一起战斗的想法后,Mami 忽然感到自己不再是孤单一人了呢。
于是,之前的谨慎的战斗作风也消失了,在对 Charlotte 的傀儡使用终曲——Tiro Finale 后,Mami 面临着即将被 Charlotte 的本体吃掉的局面。
这时,已经多次面对过 Charlotte 的 Homura 告诉了学 OI 的你这样一个性质:Charlotte 的结界中有两种具有能量的元素,一种是“糖果”,另一种是“药片”,各有 n 个。在 Charlotte 发动进攻前,“糖果”和“药片”会两两配对,若恰好糖果比药片能量大的组数比“药片”比“糖果”能量大的组数多 k 组,则在这种局面下,Charlotte 的攻击会丟失,从而 Mami 仍有消灭 Charlotte 的可能。
你必须根据 Homura 告诉你的“糖果”和“药片”的能量的信息迅速告诉 Homura 这种情况的个数。
省流:
给出两个长度均为 n 的序列 a 和 b ,保证这 2n 个数互不相同。
现要将 a 序列中的数与 b 序列中的数两两配对
求 「 ai>bj 的对数比 ai<bj 的对数恰好多 k 对」的配对方案数模 109+9。
输入格式:
第一行两个整数 n,k,含义如题目所描述。
接下来一行 n 个整数,第 i 个数表示第 i 个糖果的能量。
接下来 n 个整数,第 j 个数表示第 j 个药片的能量。
保证上面两行不会有重复的数字。
输出格式:
一个答案,表示消灭 Charlotte 的情况个数,需要对 109+9 取模。
数据范围:
对于 100% 的数据,1≤n≤2000,0≤k≤n。
显然 n,k 奇偶性不同时必然无解;否则 A>B 的对数恰好为 m=n+k2 对。
由于「恰好 m 对」这个东西不太好算,考虑「钦定 m 对」然后利用二项式反演计算
首先将 a,b 升序排序,设 dp(i,j) 表示考虑了 a 的前 i 个数,钦定了 j 对 a>b 的方案数。
转移考虑 Ai 的配对情况:
- 若不配对,则方案数为 dp(i−1,j)
- 若配对,即 b 中有 pi 个数比 ai 小,则方案数为 dp(i−1,j−1)×(pi−(j−1))
那么
dp(i,j)=dp(i−1,j)+dp(i−1,j−1)×(pi−j+1)设 fi 为钦定有 i 对 A>B 的方案数,并设 gi 为恰好有 i 对 A>B 的方案数。那么
fm=(n−m)!×dp(n,m)=n∑i=m(im)gi提示:这里钦定 i 对的意思是我们想计算 i 对的情况,但是当前的式子可能会把多于 i 对的情况算进去。
根据二项式反演有
gm=n∑i=m(−1)i−m(im)fi=n∑i=m(−1)i−m(im)(n−i)!×dp(n,i)时间复杂度 O(n2)
代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9 + 9;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
void add(int &x, int y) { (x += y) >= mod ? x -= mod : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(2333))
int fac[N], a[N], b[N], C[N][N], dp[N][N];
void init(int n)
{
fac[0] = 1; rep(i, 0, n) C[i][0] = 1;
rep(i, 1, n) fac[i] = fac[i - 1] * i % mod;
rep(i, 1, n) rep(j, 1, i) add(C[i][j] = C[i - 1][j - 1], C[i - 1][j]);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int n, k, res = 0; cin >> n >> k;
if((n ^ k) & 1) return cout << "0\n", 0;
k = (n + k) / 2; init(n);
rep(i, 1, n) { cin >> a[i]; } sort(a + 1, a + 1 + n);
rep(i, 1, n) { cin >> b[i]; } sort(b + 1, b + 1 + n);
rep(i, 0, n) dp[i][0] = 1;
rep(i, 1, n)
{
static int p = 0; while(p < n && b[p + 1] < a[i]) ++p;
rep(j, 1, n) add(dp[i][j] = dp[i - 1][j], dp[i - 1][j - 1] * (p - j + 1) % mod);
}
rep(i, k, n)
{
if((i - k) & 1) add(res, mod - C[i][k] * dp[n][i] % mod * fac[n - i] % mod);
else add(res, C[i][k] * dp[n][i] % mod * fac[n - i] % mod);
}
cout << res << '\n';
return 0;
}
参考文献: