Processing math: 100%

嘘~ 正在从服务器偷取页面 . . .

洛谷P_


洛谷P4859 已经没有什么好害怕的了 题解

题目链接:P4859 已经没有什么好害怕的了

题意

已经使 Madoka 有签订契约,和自己一起战斗的想法后,Mami 忽然感到自己不再是孤单一人了呢。

于是,之前的谨慎的战斗作风也消失了,在对 Charlotte 的傀儡使用终曲——Tiro Finale 后,Mami 面临着即将被 Charlotte 的本体吃掉的局面。

这时,已经多次面对过 Charlotte 的 Homura 告诉了学 OI 的你这样一个性质:Charlotte 的结界中有两种具有能量的元素,一种是“糖果”,另一种是“药片”,各有 n 个。在 Charlotte 发动进攻前,“糖果”和“药片”会两两配对,若恰好糖果比药片能量大的组数比“药片”比“糖果”能量大的组数多 k 组,则在这种局面下,Charlotte 的攻击会丟失,从而 Mami 仍有消灭 Charlotte 的可能。

你必须根据 Homura 告诉你的“糖果”和“药片”的能量的信息迅速告诉 Homura 这种情况的个数。

省流

给出两个长度均为 n 的序列 ab ,保证这 2n 个数互不相同。

现要将 a 序列中的数与 b 序列中的数两两配对

求 「 ai>bj 的对数比 ai<bj 的对数恰好多 k 对」的配对方案数模 109+9

输入格式

第一行两个整数 n,k,含义如题目所描述。

接下来一行 n 个整数,第 i 个数表示第 i 个糖果的能量。

接下来 n 个整数,第 j 个数表示第 j 个药片的能量。

保证上面两行不会有重复的数字。

输出格式

一个答案,表示消灭 Charlotte 的情况个数,需要对 109+9 取模。

数据范围

对于 100% 的数据,1n20000kn

显然 n,k 奇偶性不同时必然无解;否则 A>B 的对数恰好为 m=n+k2 对。

由于「恰好 m 对」这个东西不太好算,考虑「钦定 m 对」然后利用二项式反演计算

首先将 a,b 升序排序,设 dp(i,j) 表示考虑了 a 的前 i 个数,钦定了 ja>b 的方案数。

转移考虑 Ai 的配对情况:

  • 若不配对,则方案数为 dp(i1,j)
  • 若配对,即 b 中有 pi 个数比 ai 小,则方案数为 dp(i1,j1)×(pi(j1))

那么

dp(i,j)=dp(i1,j)+dp(i1,j1)×(pij+1)

fi 为钦定有 iA>B 的方案数,并设 gi 为恰好有 iA>B 的方案数。那么

fm=(nm)!×dp(n,m)=ni=m(im)gi

提示:这里钦定 i 对的意思是我们想计算 i 对的情况,但是当前的式子可能会把多于 i 对的情况算进去。

根据二项式反演有

gm=ni=m(1)im(im)fi=ni=m(1)im(im)(ni)!×dp(n,i)

时间复杂度 O(n2)

代码:

cpp
#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;
}

参考文献

[1] https://www.cnblogs.com/GXZlegend/p/11407185.html


文章作者: q779
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-ND 4.0 许可协议。转载请注明来源 q779 !
评论
你认为这篇文章怎么样?
  • 0
  • 0
  • 0
  • 0
  • 0
  • 0
评论
  • 按正序
  • 按倒序
  • 按热度
Powered by Waline v3.1.3
  目录