“ISIJ2018”table

Description

你需要将2n2*n个数字填在一个22nn列的格子中,要求满足对于每一个数都要比它左边和上方的数大,同时会钦定pp个数aia_i必须要填在第一行,qq个数bib_i必须要填在第二行,求方案数

Constraints

n106  ai,bi8000n le 10^6 a_i,b_ile 8000,保证输入数据有解(出题人原本卡空间,我就懒得去卡了。。。)

Solution

首先我们可以打表发现p=q=0p=q=0时,答案就是卡特兰数

通过观察题目性质,我们考虑从小到大,从左至右填格子,那么如果一个状态是合法的,则当前第一行填过的数必须大于等于第二行填过的数

结合p=q=0p=q=0的卡特兰数,很容易想到这就是一个括号序列的问题,钦定的数字就相当于钦定了某一个位置必须是左括号或者右括号

这个经典的问题的话直接dpdp就可以了,设dp[i][j]dp[i][j]表示考虑到第ii位,还剩jj个左括号没匹配的方案数,直接转移即可

但是因为n106n le 10^6,我们就只能dpdpm=max{ai,bi}m=max{a_i, b_i}的位置,剩下的nmn-m位可以直接计算

我们枚举在前mm位中还剩ii个左括号未匹配,在这nmn-m位中用bb个右括号,aa个左括号,且左括号数量必须小于等于右括号的数量,那么有

8-3-1

如上图,数形结合看就是问从AA点到BB点不碰到y=1y=-1有多少种走法(只↗或↘)

这个套路问题可以用总的方案数减去碰到y=1y=-1的方案数求得

而总的方案数易知为Ca+bi+a+bi2=Ca+ba+b+i2C_{a+b}^{i+frac{a+b-i}{2}}=C_{a+b}^{frac{a+b+i}{2}}

又因为i+a=bi+a=b,化简得Ca+bbC_{a+b}^{b}

而碰到y=1y=-1的方案数就是从AA点关于y=1y=-1的对称点AA'BB点的方案数,同样方式化简之后为Ca+bb+1C_{a+b}^{b+1}

那么答案即为dp[m][i](Ca+bbCa+bb+1)sum dp[m][i]*(C_{a+b}^{b}-C_{a+b}^{b+1})

只是要注意每次i+=2i+=2b++b++

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99


#define int long long
#define x first
#define y second
#define x1 X1
#define x2 X2
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) {return a < b ? a = b, 1 : 0;}
template <typename T> inline int Chkmin (T &a, T b) {return a > b ? a = b, 1 : 0;}
inline int read ()
{
int sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
return sum * fl;
}

const int Maxn = 2e6 + 100, Maxm = 8000 + 10, Mod = 998244353;

int N, M, op[Maxm], Dp[2][Maxm], fac[Maxn], inv[Maxn];

inline int Pow (int a, int b)
{
int ans = 1;
while (b)
{
if (b & 1) ans = 1ll * ans * a % Mod;
a = 1ll * a * a % Mod;
b >>= 1;
}
return ans;
}

inline void Add (int &x, int y)
{
x %= Mod, y %= Mod;
if (x < 0) x += Mod; if (y < 0) y += Mod;
x += y;
if (x >= Mod) x -= Mod; if (x < 0) x += Mod;
}

inline void Init()
{
fac[0] = 1;
for (int i = 1; i < Maxn; ++i) fac[i] = 1ll * fac[i - 1] * i % Mod;
inv[Maxn - 1] = Pow(fac[Maxn - 1], Mod - 2);
for (int i = Maxn - 2; i >= 0; --i) inv[i] = 1ll * inv[i + 1] * (i + 1) % Mod;
}

inline int C (int n, int m)
{
if (n < m) return 0;
return 1ll * fac[n] * inv[m] % Mod * inv[n - m] % Mod;
}

main()
{
freopen("table.in", "r", stdin);
freopen("table.out", "w", stdout);
N = read() * 2;
Init();
int tot = read();
while (tot--) { int x = read(); Chkmax(M, x); op[x] = 1; }
tot = read();
while (tot--) { int x = read(); Chkmax(M, x); op[x] = 2; }
Dp[0][0] = 1;
int now = 0;
for (int i = 1; i <= M; ++i)
{
now ^= 1;
for (int j = 0; j <= i; ++j)
{
Dp[now][j] = 0;
if (op[i] != 1) Add (Dp[now][j], Dp[now ^ 1][j + 1]);
if (op[i] != 2 && j) Add (Dp[now][j], Dp[now ^ 1][j - 1]);
}
}
if (N == M) { cout<<Dp[now][0]<<endl; return 0; }
N -= M;
int sum = N + 1 >> 1, ans = 0;
for (int i = (N & 1); i <= min(N, M) && sum <= N; i += 2)
{

Add (ans, 1ll * Dp[now][i] * (C(N, sum) - C(N, sum + 1)) % Mod);
++sum;
}
cout<<ans<<endl;
return 0;
}