　下図のように三角形を部分マス目として捉える．すべてのマスが $0$ の状態から始め，次の操作を $10000$ 回繰り返す：

- 辺上（マス目ではない）を通って左下から右下まで至る最短経路を一つ選び，その下側にあるマスすべてに $1$ を加える．

こうしてできた三角形は必ず整った三角形となる．逆に，最下段がすべて $10000$ であるような整った三角形 $T$ は，必ずこの操作を適当に行うことで得られる．さらに，$T$ を得る操作の方法の総数は，$T$ の整い度に一致することがわかる．\
　よって $a_{2021,1000}=5678$ となる操作を考えればよく，求める場合の数は $n$ 番目のカタラン数 $C_n$ を用いて
$$(C_{1000}\times C_{1022})^{4322}\times (C_{2022}-C_{1000}\times C_{1022})^{5678}\times {}\_{10000}\mathrm{C}\_{5678}$$
であることがわかる．これが $2$ で割りきれる最大の回数は $\bold{110261}$ である．
![figure 1](\/images\/OcMMTbLtgotbeSFCo6rhz8jpgBF1qR5EYJbw9LLZ)
公式解説
https://onlinemathcontest.com/contests/omc100/editorial/2631
**約束**
- $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}$$ と計算できる．
ユーザー解説
https://onlinemathcontest.com/contests/omc100/editorial/2631/221
　本解説では, 整数の組 $(i,j)$ は $i\geq j$ を満たす**正整数**の組を指すものとし, $(x_1,y_1)\leq(x_2,y_2)$ とは辞書式順序において $(x_1,y_1)$ は$(x_2,y_2)$ より後に来ないことを意味する.

---

　$N=10000,~M=10000-5678=4322$ とし,  以下のように左に $0$ を追加し, 下から $n(\geq 0)$ 段目, 左から $m(\geq 0)$ 個目に位置する数を $a_{n,m}$ と定義し, 整った三角形 (以下は問題文の例) を書き直す.
$$
\begin{matrix}
&a_{3,0}&a_{3,1}&a_{3,2}&a_{3,3}&a_{3,4}\\\\
&a_{2,0}&a_{2,1}&a_{2,2}&a_{2,3}\\\\
&a_{1,0}&a_{1,1}&a_{1,2}\\\\
&&a_{0,1}\\\\
\end{matrix}\quad
=\quad
\begin{matrix}
&0&0&2&2&6\\\\
&0&1&5&6\\\\
&0&1&7\\\\
&&2\\\\
\end{matrix}
$$
 
このとき, 非負整数 $\\{b_{n,m}\\},\\{c_{n,m}\\}$ を以下のように定義する.

- $b_{n,m}=a_{n,m}-a_{n,m-1}$.
- $c_{n,m}=a_{n,m}-a_{n+1,m}$.

このとき, 問題文の最後の条件より, 以下が成立. 逆にこれを満たすとき組 $(\\{b_{n,m}\\},\\{c_{n,m}\\})$ は $\\{a_{n,m}\\}$ と一対一に対応する.
-  $(i,j)\leq (2021,2021)$ について, 
$$b_{i,1}+b_{i,2}+\dots+b_{i,j}+c_{i-1,j}+c_{i-2,j}+\dots+c_{j-1,j}=N.$$
- $c_{999,1000}=M$.

そして整い度は, $\\{b_{i,j}\\},\\{c_{i,j}\\}$ を用いて以下のように表せる.
$$\prod_{(i,j)\leq(2021,2021)}\binom{b_{i,j}+c_{i-1,j}}{b_{i,j}}$$
これの総和 $S$ を 変数 $x_{i,j}\\: ((i,j) \leq (2021,2021)),y$ による形式的冪級数を用いて求める. $2$ 変数冪級数 $f(x,y)$ を

$$f(x,y):=\frac{1}{1-x-y}=\displaystyle\sum_{i=0}^{\infty}\sum_{j=0}^{\infty}\binom{i+j}{i}x^iy^j$$
 とする. 整い度の総和 $S$ は以下の冪級数 $F$ の $\displaystyle y^M \prod_{(i,j)\leq (2021,2021)} x_{i,j}^N$の係数である.
$$
F:= \prod_{(i,j)\leq (2021,2021)}f\Big(\prod_{k=j}^{i}x_{i,k}\\:\,\prod_{k=i}^{2021} x_{k,j}\Big) \quad\Big(*(i,j)=(1000,1000) のとき, f\Big(\prod_{k=j}^{i}x_{i,k}\\:\,y\prod_{k=i}^{2021} x_{k,j}\Big) \Big)
$$
( 展開したときの $x_{i,j}$ の指数が $b_{i,1}+b_{i,2}+\dots+b_{i,j}+c_{i-1,j}+c_{i-2,j}+\dots+c_{j-1,j}$ に対応し, $y$ の指数が $c_{999,1000}$ に対応している.)\
以下の補題を用いて, $\displaystyle\Bigg[\prod_{(i,j)\leq (2021,2021) }x_{i,j}^N\Bigg]F$ を求めていく. ( $y$ の多項式として展開する. )

---
**補題.**
$[x^n]\Big((ax+b)^n\dfrac{1}{1-\alpha x}\Big)=(a+b\alpha)^n$.
<details> <summary> 証明 <\/summary>
$[x^k]\Big(\dfrac{1}{1-\alpha x}\Big)=\alpha ^k, [x^k] (ax+b)^n =\displaystyle\binom{n}{k}a^kb^{n-k}$ より, 
$$\begin{aligned}
[x^n]\Big((ax+b)^n\dfrac{1}{1-\alpha x}\Big)&=\displaystyle\sum_{k=0}^{n}\Big( [x^k] \Big(\dfrac{1}{1-\alpha x}\Big)\Big)\Big([x^{n-k}] (ax+b)^n \Big)\\\\
&=\displaystyle\sum_{k=0}^{n}\binom{n}{k}(b\alpha)^{k}a^{n-k}\\\\
&=(a+b\alpha)^n
\end{aligned}$$
<\/details>

---

　$y$ の $1$ 次以下の多項式 $\\{A_{n,m}\\}$ が以下を満たすとする.

- $A_{0,0}=1$
- $A_{i,-1}=0,A_{i,i+1}=0$
- $A_{n,m}=A_{n-1,m}+A_{n,m-1}\\\: (0\leq m \leq n)$\
( $*(n,m)=(1000,1000)$ のとき, $A_{n,m}=yA_{n,m-1}+A_{n-1,m}$ )

このとき, 以下が成立.

$$
\Bigg[\prod_{(i,j)\leq (n,n)}x_{i,j}^N\Bigg] \prod_{(i,j)\leq (n,n)}f\Big(\prod_{k=j}^{i}x_{i,k}\\:\,\prod_{k=i}^{2021} x_{k,j}\Big)
=\Big(\sum_{k=0}^{n}A_{n,k}\prod_{\substack{n+1\leq t \leq 2021 \\\\ 1\leq s \leq k}}x_{t,s}\Big)^N
$$

<details> <summary> 証明 <\/summary>
　$(n,m)$ について, 以下が成立することを示せば, $(n,n)$ の場合が上の式となる.
$$
\begin{aligned}
&\Bigg[\prod_{(i,j)\leq (n,m)}x_{i,j}^N\Bigg] \prod_{(i,j)\leq (n,m)}f\Big(\prod_{k=j}^{i}x_{i,k}\\:\,\prod_{k=i}^{2021} x_{k,j}\Big)\\\\
=&\Big(\Big(\prod_{k=m+1}^{n} x_{n,k}\Big)\Big(\sum_{k=0}^{m-1}A_{n,k}\prod_{\substack{n+1\leq t \leq 2021 \\\\ 1\leq s \leq k}}x_{t,s}\Big)+A_{n,m}\prod_{\substack{n+1\leq t\leq 2021 \\\\ 1\leq s \leq m}}x_{t,s}+\sum_{k=m+1}^{n}A_{n-1,k}\prod_{\big(\substack{n+1\leq t \leq 2021 \\\\ 1\leq s \leq m}\big)\lor\big(\substack{n\leq t \leq 2021 \\\\ m+2 \leq s \leq k}\big)}x_{t,s}\Big)^N
\end{aligned}$$
　$(n,m)=(1,1)$ のとき, 成り立つことは確認できる. \
 上の式と 
$$f\Big(\prod_{k=m+1}^{n} x_{n,k}\\:\,\prod_{k=n}^{2021}x_{k,m+1}\Big)=\dfrac{1}{1-\Big(\prod_{k=m+2}^{n}x_{n,k}+\prod_{k=n+1}^{2021}x_{k,m+1}\Big)x_{n,m+1}}$$
 に補題を適用すると, $(n,m)$ について成り立つとき, 以下のように $(n,m+1)$ についても成り立つ.
$$
\begin{aligned}
&\Bigg[\prod_{(i,j)\leq (n,m+1)}x_{i,j}^N\Bigg] \prod_{(i,j)\leq (n,m+1)}f\Big(\prod_{k=j}^{i}x_{i,k} \\:\,\prod_{k=i}^{2021} x_{k,j}\Big)\\\\
=&[x_{n,m+1}^N]\Bigg(\Bigg(\Bigg[\prod_{(i,j)\leq (n,m)}x_{i,j}^N\Bigg] \prod_{(i,j)\leq (n,m)}f\Big(\prod_{k=j}^{i}x_{i,k} \\:\,\prod_{k=i}^{2021} x_{k,j}\Big)\Bigg)\times f\Big(\prod_{k=m+1}^{n} x_{n,k} \\:\,\prod_{k=n}^{2021}x_{k,m+1}\Big)\Bigg)\\\\
=&[x_{n,m+1}^N]\Bigg(\Bigg(\Big(\prod_{k=m+1}^{n} x_{n,k}\Big)\Big(\sum_{k=0}^{m-1}A_{n,k}\prod_{\substack{n+1\leq t \leq 2021 \\\\ 1\leq s \leq k}}x_{t,s}\Big)+A_{n,m}\prod_{\substack{n+1\leq t\leq 2021 \\\\ 1\leq s \leq m}}x_{t,s}+\sum_{k=m+1}^{n}A_{n-1,k}\prod_{\big(\substack{n+1\leq t \leq 2021 \\\\ 1\leq s \leq m}\big)\lor\big(\substack{n\leq t \leq 2021 \\\\ m+1\leq s \leq k}\big)}x_{t,s}\Bigg)^N\\\\
&\times\frac{1}{1-\Big(\prod_{k=m+2}^{n}x_{n,k}+\prod_{k=n+1}^{2021}x_{k,m+1}\Big) x_{n,m+1}}\Bigg) \\\\
=&\Big(\Big(\prod_{k=m+2}^{n} x_{n,k}\Big)\Big(\sum_{k=0}^{m-1}A_{n,k}\prod_{\substack{n+1\leq t \leq 2021 \\\\ 1\leq s \leq k}}x_{t,s}\Big)+A_{n,m}\Big(\prod_{\substack{n+1\leq t\leq 2021 \\\\ 1\leq s \leq m}}x_{t,s}\Big)\Big(\prod_{k=m+2}^{n}x_{n,k}+\prod_{k=n+1}^{2021}x_{k,m+1}\Big)+\sum_{k=m+1}^{n}A_{n-1,k}\prod_{\big(\substack{n+1\leq t \leq 2021 \\\\ 1\leq s \leq m+1}\big)\lor\big(\substack{n\leq t \leq 2021 \\\\ m+2\leq s \leq k}\big)}x_{t,s}\Big)^N\\\\
=&\Big(\Big(\prod_{k=m+2}^{n} x_{n,k}\Big)\Big(\sum_{k=0}^{m}A_{n,k}\prod_{\substack{n+1\leq t \leq 2021 \\\\ 1\leq s \leq k}}x_{t,s}\Big)+(A_{n,m}+A_{n-1,m+1})\prod_{\substack{n+1\leq t\leq 2021 \\\\ 1\leq s \leq m+1}}x_{t,s}+\sum_{k=m+2}^{n}A_{n-1,k}\prod_{\big(\substack{n+1\leq t \leq 2021 \\\\ 1\leq s \leq m+1}\big)\lor\big(\substack{n\leq t \leq 2021 \\\\ m+2\leq s \leq k}\big)}x_{t,s}\Big)^N\\\\
=&\Big(\Big(\prod_{k=m+2}^{n} x_{n,k}\Big)\Big(\sum_{k=0}^{m}A_{n,k}\prod_{\substack{n+1\leq t \leq 2021 \\\\ 1\leq s \leq k}}x_{t,s}\Big)+A_{n,m+1}\prod_{\substack{n+1\leq t\leq 2021 \\\\ 1\leq s \leq m+1}}x_{t,s}+\sum_{k=m+2}^{n}A_{n-1,k}\prod_{\big(\substack{n+1\leq t \leq 2021 \\\\ 1\leq s \leq m+1}\big)\lor\big(\substack{n\leq t \leq 2021 \\\\ m+2\leq s \leq k}\big)}x_{t,s}\Big)^N\end{aligned}$$
 $(n,n)$ から $(n+1,1)$ についても同様に示される.
<\/details>

特に,
$$\begin{aligned}\Bigg[\prod_{(i,j)\leq (2021,2021) }x_{i,j}^N\Bigg]F&=\Big(\sum_{k=0}^{2021}A_{2021,k}\Big)^N\\\\
&=(A_{2022,2022})^N
\end{aligned}$$
$\\{A_{n,m}\\}$ の漸化式より $y$ の一次式 $A_{n,m}$ について以下が成立

- ($A_{n,m}$ の係数の総和) $=$ ( $(0,0)$ から $x\geq y$ の領域内で $x,y$ いずれかの正方向に $1$ 進むことを繰り返し, $(n,m)$ に到達する経路数)
- ($A_{n,m}$ の $y$ の係数) $=$ ( $(0,0)$ から $x\geq y$ の領域内で $x,y$ いずれかの正方向に $1$ 進むことを繰り返し, $(1000,1000)$ を通り, $(n,m)$ に到達する経路数)

 よって, カタラン数 $C_n:=\displaystyle\frac{1}{n+1}\binom{2n}{n}$ を用いて以下のようになる. 
$$(A_{2022,2022})^N=((C_{2022}-C_{1000}C_{1022})+C_{1000}C_{1022}\times y)^N$$
特に, 以下に示す $y^M$ の係数が求める整い度の総和となる. 
$$\binom{N}{M}(C_{1000}C_{1022})^M(C_{2022}-C_{1000}C_{1022})^{N-M}$$
形式的冪級数を用いる解法
https://onlinemathcontest.com/contests/omc100/editorial/2631/606
　以下のように，正三角形状に非負整数を並べた配列が**整った三角形**であるとは，最下行以外に位置する任意の数について，そのすぐ下に位置する左右 $2$ つの数の最小値以下であることを指します．以下は $4$ 段の**整った三角形**の一例となっています．
$$
\begin{aligned}
~ &  & ~ & & ~ & & 0 & & ~ & & ~ & & ~ \\\\
~ &  & ~ & & 1 & & ~ & & 2 & & ~ & & ~ \\\\
~ &  & 1 & & ~ & & 5 & & ~ & & 2 & & ~ \\\\
2 &  & ~ & & 7 & & ~ & & 6 & & ~ & & 6
\end{aligned}
$$
　また，$n$ 段の**整った三角形**の**整い度**を，以下に示す二項係数の総積で定めます．\
　ただし，上から $x(\geq 1)$ 段目，左から $y(\geq 1)$ 個目に位置する数を $a_{x,y}$ で表すものとし，$i=0,1,\ldots$ に対し $a\_{i,0}=0$ とします．
$$
\prod_{x=2}^{n}\prod_{y=1}^{x-1} \binom{a_{x,y}-a_{x-2,y-1}}{a_{x,y}-a_{x-1,y}}
$$
　$2022$ 段の**整った三角形**であって，以下をみたすものすべてについて，それらの**整い度**の総和を $S$ とします．$S$ が $2$ で割りきれる最大の回数を求めてください． 
$$a_{2022,i}=10000 \quad (1\leq i\leq 2022),\qquad a_{2021,1000}=5678$$