C++14(g++5.4) 解法, 执行用时: 60ms, 内存消耗: 43784K, 提交时间: 2020-09-20 10:55:35

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
	int X=0,w=1; char c=getchar();
	while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
	while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
	return X*w;
}

const int N=1000+10,M=10+10;
const int mod=1e9+9;

int n,m,k;
int a[N],b[N];
int dp[M][N][N];

int main() {
	n=read(),m=read(),k=read();
	for (int i=1;i<=n;++i) a[i]=read();
	for (int i=1;i<=m;++i) b[i]=read();
	sort(a+1,a+n+1),sort(b+1,b+m+1);
	for (int i=0;i<=n;++i)
		for (int j=0;j<=m;++j) dp[0][i][j]=1;
	for (int i=1;i<=k;++i) {
		for (int p=1;p<=n;++p)
			for (int q=1;q<=m;++q)
				if (a[p]>b[q]) dp[i][p][q]=dp[i-1][p-1][q-1];
		for (int p=1;p<=n;++p)
			for (int q=1;q<=m;++q)
				dp[i][p][q]=(dp[i][p][q]+dp[i][p][q-1])%mod;
		for (int p=1;p<=n;++p)
			for (int q=1;q<=m;++q)
				dp[i][p][q]=(dp[i][p][q]+dp[i][p-1][q])%mod;
	}
	printf("%d\n",dp[k][n][m]);
	return 0;
}

C++ 解法, 执行用时: 63ms, 内存消耗: 43640K, 提交时间: 2021-11-10 14:49:06

#include <bits/stdc++.h>
const int NN = 1004, mo = 1e9 + 9;
#define _forr(i, a, b) for (int i = (a); i <= (int)(b); ++i)
using namespace std;
int A[NN], B[NN], f[12][NN][NN];
int main() {
  int n, m, p;
  scanf("%d%d%d", &n, &m, &p);
  _forr(i, 1, n) scanf("%d", &A[i]);
  _forr(i, 1, m) scanf("%d", &B[i]);
  sort(A + 1, A + n + 1), sort(B + 1, B + m + 1);
  _forr(i, 0, n) _forr(j, 0, m) f[0][i][j] = 1;
  _forr(i, 1, p) {
    _forr(j, 1, n) _forr(k, 1, m) 
      if (A[j] > B[k]) f[i][j][k] = f[i - 1][j - 1][k - 1];
    _forr(j, 1, n) _forr(k, 1, m)(f[i][j][k] += f[i][j][k - 1]) %= mo;
    _forr(j, 1, n) _forr(k, 1, m)(f[i][j][k] += f[i][j - 1][k]) %= mo;
  }
  printf("%d", f[p][n][m]);
}