[BZOJ 3622] 已经没有什么好害怕的了 手动反演

题意

  给定两个大小为 n 的集合 A = {a[1], a[2], ..., a[n]} , B = {b[1], b[2], ..., b[n]} , 元素两两不同.

  定义 L(A) 为 A 生成的排列的集合.

  给定 K , 求 $\sum_{X \in L(A), Y \in L(B)} [\sum_{k = 1} ^ n [X_k > Y_k] - \sum_{k = 1} ^ n [X_k < Y_k] = K]$ .

  1 <= n <= 2000, 0 <= K <= n .

分析

  令 $K = \frac{n + K}{2}$ , 求恰好存在 K 个 X[i] > Y[i] 的排列有多少对.

  设 f[i] 表示钦定有 i 个位, X[i] > Y[i] , 并且不考虑其他位.

  f[i] 可以通过 DP 求得.

  F[i][j] = F[i-1][j] + F[i-1][j-1] * (cnt[i] - (j-1)) .

  不能直接用 f[K] * (n-K)! + f[K+1] * (n-(K+1))! - ...

  因为从第二项开始算的次数都不是一次, 而是一个谜之二项式系数的乘积的和.

  设 g[i] 表示恰好有 i 个位, X[i] > Y[i] .

  g[n] = f[n] .

  $g[i] = f[i] - \sum_{j = i+1} ^ n g[j] \binom{j}{i}$ .

  这里的做法, 与 "手动的莫比乌斯反演" 是一个原理.

小结

  对于这类恰好有 K 个位的问题, 我们可以考虑手动反演.

  G[K] 表示恰好有 K 个位, F[K] 表示钦定有 K 个位.

  G[n] = F[n] .

  G[i] = F[i] - ∑ G[j] * 迷之系数.

实现

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <cctype>
 5 #include <algorithm>
 6 using namespace std;
 7 #define F(i, a, b) for (register int i = (a); i <= (b); i++)
 8 #define P(i, a, b) for (register int i = (a); i >= (b); i--)
 9 inline int rd(void) {
10     int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == ‘-‘) f = -1;
11     int x = 0; for (; isdigit(c); c = getchar()) x = x*10+c-‘0‘; return x*f;
12 }
13
14 const int N = 2005;
15 const int MOD = (int)1e9 + 9;
16
17 int n, K, C[N][N], fac[N], A[N], B[N], cnt[N];
18 int f[N], g[N];
19
20 int main(void) {
21     #ifndef ONLINE_JUDGE
22         freopen("bzoj3622.in", "r", stdin);
23     #endif
24
25     n = rd(), K = rd();
26     if ((K + n) & 1) return puts("0"), 0;
27     K = (K + n) >> 1;
28
29     F(i, 0, n) {
30         C[i][0] = 1;
31         F(j, 1, i)
32             C[i][j] = (C[i-1][j] + C[i-1][j-1]) % MOD;
33     }
34     fac[0] = 1;
35     F(i, 1, n) fac[i] = 1LL * fac[i-1] * i % MOD;
36
37     F(i, 1, n) A[i] = rd(); F(i, 1, n) B[i] = rd();
38     sort(A+1, A+n+1), sort(B+1, B+n+1);
39     for (int cur = 1, _cur = 0; cur <= n; cur++) {
40         while (_cur+1 <= n && B[_cur+1] < A[cur])
41             _cur++;
42         cnt[cur] = _cur;
43     }
44
45     f[0] = 1;
46     F(i, 1, n)
47         P(j, i, 1)
48             f[j] = (f[j] + 1LL * f[j-1] * (cnt[i] - (j-1))) % MOD;
49
50     g[n] = f[n];
51     P(i, n-1, K) {
52         g[i] = 1LL * f[i] * fac[n-i] % MOD;
53         F(j, i+1, n)
54             g[i] = (g[i] - 1LL * g[j] * C[j][i]) % MOD;
55     }
56     printf("%d\n", (g[K] + MOD) % MOD);
57
58     return 0;
59 }
时间: 08-17

[BZOJ 3622] 已经没有什么好害怕的了 手动反演的相关文章

BZOJ 3622(已经没有什么好害怕的了-Dp+容斥原理)

3622: 已经没有什么好害怕的了 Time Limit: 10 Sec  Memory Limit: 256 MB Submit: 7  Solved: 6 [Submit][Status] Description Input Output Sample Input 4 2 5 35 15 45 40 20 10 30 Sample Output 4 HINT Source 2014湖北省队互测week2 PS:本题的数据中能量互不相同. 1.我们计算出糖果>药片的组数=k 2.我们计算出f[

[BZOJ 3622]已经没有什么好害怕的了

世萌萌王都拿到了,已经没有什么好害怕的了——    (作死) 笑看哪里都有学姐,真是不知说什么好喵~ 话说此题是不是输 0 能骗不少分啊,不然若学姐赢了,那么有头的学姐还能叫学姐吗?  (作大死) 这题的数据就告诉我们这是赤裸裸的 dp ,不过要加个容斥而已 注意到我们可以算出一共需要 s 组满足糖果数 > 药片数 (在这里显然有个特判,即 n-k 为奇数时,答案一定为 0 ) 我们将两个读入的数组排序 令 next[i] 表示最大的 j 满足 糖果[i]>药片[j] 令 f[i][j] 表示

[BZOJ 3622]已经没有什么好害怕的了(Dp+容斥原理)

Description 图片略 Solution 对啊,已经没有什么好害怕的了 没有头的麻美学姐还是很萌的(雾 排序预处理p[i]为b中小于a[i]的最大的数的标号 f[i][j]表示前i个糖果使得糖果大于药片的至少有j组 则f[i][j]=f[i-1][j]+f[i-1][j-1]*(p[i]-j+1) 容斥得g[j]=f[n][j]*(n-j)!-∑g[k]*C(j,k) (j+1<=k<=n) #include<iostream> #include<cstdio>

BZOJ 3622 已经没有什么好害怕的了 动态规划+容斥原理

题目大意:给定两个长度为n个序列,保证这2n个数字两两不同,求有多少匹配满足a[i]>b[i]的数对数比a[i]<b[i]的数对数多k もう何も怖くない 题解:http://www.cnblogs.com/dyllalala/p/3900077.html OTZ 神思路根本就是想不到啊QAQ でも...もう何も怖くない...(大雾 此外我们可以引入一下WTY公式: C[i][j]=C[i-1][j]*C[i-1][j-1] ...脑残怎么治啊... #include <cstdio>

bzoj 3622 DP + 容斥

LINK 题意:给出n,k,有a,b两种值,a和b间互相配对,求$a>b$的配对组数-b>a的配对组数恰好等于k的情况有多少种. 思路:粗看会想这是道容斥组合题,但关键在于如何得到每个a[i]大于b的组数. 不妨从整体去考虑,使用$f[n][j]$代表前n个中有j组$a[i]>b[i]$,很容易得到转移式$f[n][j]=f[n-1][j]+f[n-1][j-1]*(cnt[n]-(j-1))$,其中$cnt[i]$为比a[i]小的b[]个数 但是仔细思考该式子含义会发现,$f[n][j

【bzoj 3622】已经没有什么好害怕的了

题目 看到这个数据范围就发现我们需要一个\(O(n^2)\)的做法了,那大概率是\(dp\)了 看到恰好\(k\)个我们就知道这基本是个容斥了 首先解方程发现我们需要使得\(a>b\)的恰好有\(\frac{n+k}{2}\)组 如果不整除我们直接输出\(0\)就好了 之后开始使用套路,直接广义容斥 \[ans=\sum_{i=k}^n(-1)^{i-k}\binom{i}{k}g_i\] \(g_i\)表配出至少\(i\)对\(a>b\)的情况 显然我们现在需要一个\(dp\)来算一下\(g

bzoj 3622

直接算 $a_i>b_i$ 对数恰为 $k$ 的不好算 那么可以先算 $a_i>b_i$ 对数至少 $k$ 的 这个排序后随便dp一下就好 那么再除了一下 用 $f_i$ 表示 $a_i>b_i$ 对数至少i的方案数 用 $g_i$ 表示 $a_i>b_i$ 对数恰为i的方案数 那么 $g_i=f_i(n-i)!-\sum_{j=i+1}^n g_jC(j,i)$ 其中,$(n-i)!$ 表示除了这 $i$ 个以外的所有元素的排列方式,$g_jC(j,i)$ 表示在 $j$ 个中任

【BZOJ 3994】3994: [SDOI2015]约数个数和(莫比乌斯反演)

3994: [SDOI2015]约数个数和 Description 设d(x)为x的约数个数,给定N.M,求   Input 输入文件包含多组测试数据. 第一行,一个整数T,表示测试数据的组数. 接下来的T行,每行两个整数N.M. Output T行,每行一个整数,表示你所求的答案. Sample Input 2 7 4 5 6 Sample Output 110 121 HINT 1<=N, M<=50000 1<=T<=50000 Source Round 1 感谢yts199

BZOJ 2440: [中山市选2011]完全平方数 二分答案 + 容斥原理 + 莫比乌斯反演

http://www.lydsy.com/JudgeOnline/problem.php?id=2440 第一道莫比乌斯反演的题目. 二分答案 + 容斥那里还是挺好想的. 二分一个答案val,需要[1, val]之间存在的合法数字个数 >= k即可. 怎么判断呢?可以容斥,开始的时候有ans = val个,但是这里明显有些数字不符合. ans -= ([1...val]中有多少个2^2倍  + [1...val]中有多少个3^2倍 + [1...val]中有多少个5^2倍) ...... 但是减