TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P2966
  • Problem
  • P2966【2014湖北省队互测week2】已经没什么好害怕的了
    Limits : Time Limit : 1000 MS   Memory Limit : 265536 KB
    Judgment Tips : 1s
    Description

            已经使Modoka有签订契约,和自己一起战斗的想法后,Mami忽然感到自己不再是孤单一人了呢。
            于是,之前的谨慎的战斗作风也消失了,在对Charlotte的傀儡使用终曲——Tiro Finale后,Mami面临着即将被Charlotte的本体吃掉的局面。
            这时,已经多次面对过Charlotte的Homura告诉了学OI的你这样一个性质——Charlotte的结界中有两种具有能量的元素——一种是“糖果”,另一种是“药片”,每种各有n个。在Charlotte发动进攻前,“糖果”和“药片”会两两配对,若恰好“糖果”比“药片”能量大的组数比“药片”比“糖果”能量大的组数多k组,则在这种局面下,Charlotte的攻击会丢失,从而Mami仍有消灭Charlotte的可能。你必须根据Homura告诉你的“糖果”和“药片”的能量的信息迅速告诉Homura这种情况的个数。

    Input Format

            第一行两个整数n,k,含义如题目描述。
            接着第二行n个整数,第i个数表示第i个糖果的能量。
            第三行n个整数,第j个数表示第j个药片的能量。

    Output Format

            一个整数,表示消灭Charlotte的情况个数。答案可能会很大,所以mod (109+9)

    Sample Input

    4 2
    5 35 15 45
    40 20 10 30

    Sample Output

    4

    Hint

    样例解释:
    正确的组合为: (5-40,35-20,15-10,45-30),(5-40,45-20,15-10,35-30),(45-40,5-20,15-10,35-30)以及(45-40,35-20,15-10,5-30)。

    数据范围:
    约定:给出的2*n个能量值两两不同
    对于10%的数据:1<=n<=10
    对于40%的数据:1<=n<=500
    对于100%的数据:1<=n<=2000,0<=k<=n


    Source  感谢clearday命题,感谢nodgd放题