OMC100(F)

約束

• $n=2022,m=10000$ とする．
• 数列は $0$ -indexed とする．(行列の列番号・行番号も含む)
• 行列 $A$ の $(i,j)$ 成分 (第 $i$ 行第 $j$ 列) を $A[i,j]$ で表す．

　以下の条件をすべて満たす $n + 1$ 次正方行列 $U$ を整った行列 という．

• $i = 0 \lt j$ のとき，$U[i,j] = 0$．
• $i = j$ のとき，$U[i,j] = m$．
• $i \lt j$ のとき，$U[i,j]$ は $U[i+1,j],U[i,j-1]$ の最小値よりも小さい．
• $i \gt j$ のとき，$U[i,j] = 0$．

　整った行列 $U$ の整い度 $f(U)$ を， $$f(U) = \prod_{i=1}^{n-1} \prod_{j=i}^{n-1} \binom{U[i,j] - U[i-1,j+1]}{U[i,j] - U[i-1,j]}$$ と定義する．
　整った行列は，「最下行がすべて $m$ であるような $n$ 段の整った三角形」と，整い度の定義も含めて等価で，制約「 $a_{n-1,1000} = 5678$ 」は「 $U[1000,1001] = 5678$ 」と等価．
よって，$S$ は，$U[1000,1001] = 5678$ なる整った行列 $U$ の整い度の総和．

　$n + 1$ 行 $m$ 列のマス目に，$n$ 以下の整数が書き込まれ，それらが以下の条件をすべて満たすとき，これを整い盤という．

• 第 $0$ 行には，すべて $0$ が書かれる．
• 各列で，書かれた数は上から下に単調非減少である．
• 第 $i$ 行には，すべて $i$ 以上の整数が書かれる．

整い盤 $B$ が整った行列 $U$ を表すとは，以下の条件を満たすことをいう．なお，このような $U$ は一意に存在することが証明できる．

• $B$ の第 $i$ 行には，$j$ 以上の整数がちょうど $U[i,j]$ 個書かれる．

　第 $i - 1$ 行までの書き込み方と，第 $i$ 行における $j$ 未満の整数の書き込み方が既に決まっているとする．( $i,j$ は $1$ 以上 $n$ 以下の整数)
　第 $i$ 行で $j$ を書き込めるマスは，真上のマスが $j$ 以下であるような $m - U[i-1,j+1]$ 個のマスから，$j$ 未満の整数に既に占有されている $m - U[i,j]$ 個のマスを除いた，$U[i,j] - U[i-1,j+1]$ 個のマスである．
　この中から $U[i,j] - U[i,j+1]$ 個のマスを選んで $j$ を書き込むのであるから，$U$ を表す整い盤 について，$i$ 行目の $j$ の書き込み方は，$i$ 行目の $j-1$ までの書き込み方ごとに $\dbinom{U[i,j] - U[i-1,j+1]}{U[i,j] - U[i-1,j]}$ 通り存在する．
　よって，整った行列 $U$ の整い度は，$U$ を表す整い盤の個数に等しい．

　ある整い盤 $B$ が表す整った行列 $U$ が $U[1000,1001] = 5678$ を満たすことは，$B$ の $1000$ 行目にちょうど $4322$ 個の $1000$ が書かれていることと同値．
　非負整数 $k$ に対し，$C_k$ を $k$ 番目のカタラン数 $(= \frac{(2k)!}{k!(k+1)!})$ とする．
　整い盤の一列としてありうる数列は $C_n$ 個で，そのうち第 $1000$ 項が $1000$ であるものは $C_{1000} \cdot C_{n-1000}$ 個であるから， $1000$ 行目にちょうど $4322$ 個の $1000$ が書かれた整い盤の個数は， $${}_{10000} \mathrm{C} _{4322} (C_{1000} \cdot C_{n-1000})^{4322} (C_n - C_{1000} \cdot C_{n-1000}) ^{5678}$$ であり，これが $S$ に等しい．
　これが $2$ で割り切れる最大の回数は，ルジャンドルの定理やクンマーの定理により， $$7 + 15 \times 4322 + 8 \times 5678 = \textbf{110261}$$ と計算できる．