P2966【2014湖北省队互测week2】已经没什么好害怕的了
问题描述
已经使Modoka有签订契约,和自己一起战斗的想法后,Mami忽然感到自己不再是孤单一人了呢。
于是,之前的谨慎的战斗作风也消失了,在对Charlotte的傀儡使用终曲——Tiro Finale后,Mami面临着即将被Charlotte的本体吃掉的局面。
这时,已经多次面对过Charlotte的Homura告诉了学OI的你这样一个性质——Charlotte的结界中有两种具有能量的元素——一种是“糖果”,另一种是“药片”,每种各有n个。在Charlotte发动进攻前,“糖果”和“药片”会两两配对,若恰好“糖果”比“药片”能量大的组数比“药片”比“糖果”能量大的组数多k组,则在这种局面下,Charlotte的攻击会丢失,从而Mami仍有消灭Charlotte的可能。你必须根据Homura告诉你的“糖果”和“药片”的能量的信息迅速告诉Homura这种情况的个数。
输入格式
第一行两个整数n,k,含义如题目描述。
接着第二行n个整数,第i个数表示第i个糖果的能量。
第三行n个整数,第j个数表示第j个药片的能量。
输出格式
一个整数,表示消灭Charlotte的情况个数。答案可能会很大,所以mod (109+9)
样例输入
4 2
5 35 15 45
40 20 10 30
样例输出
4
数据范围:
约定:给出的2*n个能量值两两不同
对于10%的数据:1<=n<=10
对于40%的数据:1<=n<=500
对于100%的数据:1<=n<=2000,0<=k<=n
先将$A_i$和$B_i$排序
考虑如何计算恰有K对$A_i>B_i$的方案数。
令$F[i]$表示恰有$i$对的方案数,令$f[i][j]$表示$A_i$的前$i$个数有$j$对的方案数。
令$t[i]$表示$B$中小于$A_i$的数的数量。
那么有转移方程$f[i][j]=f[i-1][j]+f[i-1][j-1]*(t[i]-j+1)$,$t[i]-j+1$表示总共有$t[i]$个数可以与$A[i]$匹配,而其中已经匹配了$j-1$个。
然后令$G[i]=(n-i)!f[n][i]$,注意到,这里的$G[i]$意思是先确定$i$对$A_x>B_x$,然后剩下的随便排列。
考虑$G[i]$与$F[i]$的关系,能够推出
$$G[i]=\sum_{j=i}^{n}C_{j}^{i}F[j]$$
这里我们考虑对于$G[i]$,肯定至少有$i$对,但剩下的任意排列可能使得对数增加,同时可能造成重复。因此枚举总共有多少对,然后考虑重复,对于有$j$对的方案,在$G[i]$中被重复算的次数恰好就是$C_{j}^{i}$,意思是从这$j$对中选出$i$对作为一开始在$f[n][i]$中确定的$i$对。
最后二项式反演得到$$F[i]=\sum_{j=i}^{n}(-1)^{j-i}C_{j}^{i}G[j]$$
总时间复杂度$O(n^2)$
代码:
1 |
|