Vì ~N~, ~M~ và ~K~ khá nhỏ nên ta có thể quy hoạch động với ~O(N \times M \times K)~.

Với ~dp_{i,j,k}~ là số lượng ~k~ thẻ bải được chọn sau khi ta xét ~i~ thẻ bài đầu tiên của ~Neko~ và ~j~ thẻ bài đầu tiên của đối thủ. Ta có công thức chuyển trạng thái:

~dp_{i,j,k}~ = ~dp_{i-1,j,k} + dp_{i,j-1,k} - dp_{i-1,j-1,k}~

Nếu thẻ bài thứ ~i~ của ~Neko~ lớn hơn thẻ bài thứ ~j~ của đối thủ. Ta sẽ cộng ~dp_{i-1,j-1,k-1}~ vào ~dp_{i,j,k}~.

Code mẫu

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int value;
    bool isFj;

    bool operator<(Node const& other) const {
        if (value == other.value) {
            return isFj && !other.isFj;
        }
        return value < other.value;
    }
};

#define NMAX 1000
#define KMAX 10

#define MOD 1000000009

unsigned int dp[2 * NMAX + 1][KMAX + 1][KMAX + 1];

int main() {
    int n, m, k;
    cin >> n >> m >> k;

    vector<Node> nodes;
    for (int i = 0; i < n; i++) {
        Node n;
        scanf("%d", &n.value);
        n.isFj = true;
        nodes.push_back(n);
    }
    for (int i = 0; i < m; i++) {
        Node n;
        scanf("%d", &n.value);
        n.isFj = false;
        nodes.push_back(n);
    }

    sort(nodes.begin(), nodes.end());

    for (int i = 0; i <= k; i++) {
        for (int j = 0; j <= k; j++) {
            dp[nodes.size()][i][j] = (i == 0 && j == 0 ? 1 : 0);
        }
    }

    for (int pos = nodes.size() - 1; pos >= 0; pos--) {
        for (int i = 0; i <= k; i++) {
            for (int j = 0; j <= k; j++) {
                if (j > i) {
                    dp[pos][i][j] = 0;
                } else {
                    if (nodes[pos].isFj) {
                        dp[pos][i][j] = (dp[pos+1][i][j] + (i > 0 ? dp[pos+1][i-1][j] : 0)) % MOD;
                    } else {
                        dp[pos][i][j] = (dp[pos+1][i][j] + (j > 0 ? dp[pos+1][i][j-1] : 0)) % MOD;
                    }
                }
            }
        }
    }

    printf("%d\n", dp[0][k][k]);
}