Team Building

题目描述

每年，农夫 John 都会带着他的 $N$ 头奶牛去州博览会参加“最佳展牛”比赛。他的宿敌农夫 Paul 也会带着他的 $M$ 头奶牛来参赛（$1 \leq N \leq 1000, 1 \leq M \leq 1000$）。 在活动中，这 $N + M$ 头奶牛每头都会得到一个整数分数。然而，今年的最终比赛将基于由 $K$ 头奶牛组成的队伍（$1 \leq K \leq 10$）来决定，规则如下：农夫 John 和农夫 Paul 分别从各自的奶牛中选出 $K$ 头组成队伍参赛。随后将两支队伍中的奶牛配对：FJ 队中分数最高的奶牛与 FP 队中分数最高的奶牛配对，FJ 队中分数第二高的奶牛与 FP 队中分数第二高的奶牛配对，依此类推。 如果在每一对配对中，FJ 的奶牛分数都更高，则 FJ 获胜。 请帮助 FJ 统计他和 FP 选择队伍使得 FJ 获胜的不同方式数。也就是说，需要统计每一个不同的组合对（FJ 选择的 $K$ 头奶牛的集合，FP 选择的 $K$ 头奶牛的集合）且 FJ 获胜的情况。将答案对 1,000,000,009 取模后输出。

输入格式

第一行输入包含 $N$、$M$ 和 $K$。$K$ 的值不会大于 $N$ 或 $M$。 第二行包含 FJ 的 $N$ 头奶牛的分数。 第三行包含 FP 的 $M$ 头奶牛的分数。

输出格式

输出 FJ 和 FP 选择队伍使得 FJ 获胜的方案数，并对 1,000,000,009 取模。

10 10 3
1 2 2 6 6 7 8 9 14 17
1 3 8 10 10 16 16 18 19 19

382

提示

题目作者：Brian Dean 和 William Luo

标签: USACO|2016|Platinum

来源

USACO|2016|Platinum