
 100通过
 214提交
 题目提供者 FarmerJohn2
 评测方式 云端评测
 标签 USACO 2016 高性能
 难度 提高+/省选
 时空限制 1000ms / 128MB
最新讨论 显示
题目背景
欢迎提供翻译，请直接在讨论区发帖，感谢你的贡献。
题目描述
Every year, Farmer John brings his $N$ cows to compete for "best in show" at the state fair. His archrival, Farmer Paul, brings his $M$ cows to compete as well ($1 \leq N \leq 1000, 1 \leq M \leq 1000$).
Each of the $N + M$ cows at the event receive an individual integer score. However, the final competition this year will be determined based on teams of $K$ cows ($1 \leq K \leq 10$), as follows: Farmer John and Farmer Paul both select teams of $K$ of their respective cows to compete. The cows on these two teams are then paired off: the highestscoring cow on FJ's team is paired with the highestscoring cow on FP's team, the secondhighestscoring cow on FJ's team is paired with the secondhighestscoring cow on FP's team, and so on. FJ wins if in each of these pairs, his cow has the higher score.
Please help FJ count the number of different ways he and FP can choose their teams such that FJ will win the contest. That is, each distinct pair (set of $K$ cows for FJ, set of $K$ cows for FP) where FJ wins should be counted. Print your answer modulo 1,000,000,009.
输入输出格式
输入格式：The first line of input contains $N$, $M$, and $K$. The value of $K$ will be no larger than $N$ or $M$.
The next line contains the $N$ scores of FJ's cows.
The final line contains the $M$ scores of FP's cows.
输出格式：Print the number of ways FJ and FP can pick teams such that FJ wins, modulo 1,000,000,009.