数字(number)
为了庆祝祖国的66岁生日， 小Z拿来了一个(2)行$ n $列的方格， 现在他想往里面填入$1,2,…,2n $的数字， 使得每行从左到右递增， 每一列从上到下递增。
小Z随便填了几个数字之后想考一考你， 现在总共有多少种方案呢？Input
第一行包含一个整数(n)。
接下来(2)行， 每行(n)个整数， 若是0则表示未填入， 否则表示已填入这个数字。Output
输出一行一个数字表示答案，不对任何数取模。
Example
输入 #1
(3)
(0) (3) (0)
(2) (0) (0)输出 #1
(2)
Scoring
对于 10%的数据， 满足 (n≤5)；
对于 30%的数据， 满足 (n≤20)；
对于 100%的数据， 满足 (n≤1000)；
知道是DP但是不会，比赛敲了个暴力还错了
真的废物
————————————————————————————————————————
先来填几个看看
左上角必填1
| (1) | (-) | (-) | (...) |
|---|---|---|---|
| (-) | (-) | (-) | (...) |
2有两个位置可以填
| (1) | (2) | (-) | (...) |
|---|---|---|---|
| (-) | (-) | (-) | (...) |
| 或 | |||
| (1) | (-) | (-) | (...) |
| :-: | :-: | :-: | :-: |
| (2) | (-) | (-) | (...) |
对于上面那种填法，3可以填
| (1) | (2) | (3) | (...) |
|---|---|---|---|
| (-) | (-) | (-) | (...) |
| 或 | |||
| (1) | (2) | (-) | (...) |
| :-: | :-: | :-: | :-: |
| (3) | (-) | (-) | (...) |
下面那种则是
| (1) | (3) | (-) | (...) |
|---|---|---|---|
| (2) | (-) | (-) | (...) |
(...)
可以看出以下两个性质
1.填好的格子都是挨在一起的
2.第一行填的数字个数必不少于第二行（用反证法非常容易，这里就不证了，因为我讲不清楚
这俩性质说明位置((i,j))的种类必来自于((i,j-1))与((i-1,j))（如果有这个点）
因此，只要从((1,1))开始推就好了
如果碰上已经填好的，就判断一下这里填的是不是刚好就是我们本来就打算填的数，是的话就给这个点加上我们从前面推过来的数，不是的话就不加
递推式：(f[i][j])表示第一列填了(i)个数，第二列填了(j)个数，(f[i][j])本身指做到当前情况所拥有的种类数
得 (f[i][j]=f[i-1][j]+f[i][j-1])
另，我们看到题目的输出格式非常玄妙：
输出一行一个数字表示答案，不对任何数取模
不对任何数取模
当这个2行数组全空时，答案为卡特兰数，肥肠大，所以要写个高精
讲完了，看代码。
（虽然我懂了但是代码还是挂，感谢whx大佬的指导，以下代码大量参考他写的正解）
//:D
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
const long long maxn = 1e18;
struct code {//高精
long long ch[55];
int len;
void work (){//进位
for (int i = 1; i <= len; i++)
if (ch[i] >= maxn) ++ch[i + 1], ch[i] -= maxn;
while (len > 1 && ch[len] == 0) --len;
}
void add (code x){//加一个数
len = max (len, x.len) + 1;
for (int i = 1; i <= len; i++) ch[i] += x.ch[i];
work();
}
void print(){
work();
printf("%lld",ch[len--]);
for(int i = len; i >= 1; i--)
printf("%018lld", ch[i]);
}
} f[N][N];
int n, k[2][N], ok[N<<1];//ok[i]==1表示i已经被填过表格
int main(){
scanf("%d", &n);
for (int i = 1; i <= n; i++) {scanf("%d", &k[0][i]); ok[k[0][i]] = 1;}
for (int i = 1; i <= n; i++) {scanf("%d", &k[1][i]); ok[k[1][i]] = 1;}
f[0][0].ch[1] = 1, f[0][0].len = 1;
for (int i = 1; i <= n; i++)
for (int j = 0; j <= i; j++){
int p = i + j;//现在在(i,j)，填到i+j
if (i > j &&
((k[0][i] == 0 && ok[p] == 0) || k[0][i] == p))
//如果上一排填的比下一排多（合法） 并且
//这个位置没有被填过数且要填的数没有被用过 或者 这个位置填好的就是这个数
f[i][j] = f[i - 1][j];
if (j && ((k[1][j] == 0 && ok[p] == 0) || k[1][j] == p))
f[i][j].add(f[i][j - 1]);
}
f[n][n].print();
return 0;
}