# OMC230F 思考過程

[公式解説](https://onlinemathcontest.com/contests/omc230/editorial/7789)と本質的には変わらないだろうが、数学初心者の競プロerなりに考えた方法を書き留めておく。私はこちらの方が考えやすかった。

`A` と `B` を `0` に、`C` を `1` に置き換えた文字列を考える。たとえば、`ACBAC` は `01001` となる。定義より、`0` が隣り合うことがあっても、`1` が隣り合うことはない。

このようにしたとき、操作は以下のように置き換えられる。

* `0` と `1` の間には、`0` を挿入する。
* `1` と `0` の間には、`0` を挿入する。
* `0` と `0` の間には、`1` を挿入する。

以下のようなDPを考える。

* $DP_s[i]=$ `00` に $i$ 回操作を行ったときの、`1` の個数
* $DP_d[i]=$ `01` または `10` に $i$ 回操作を行ったときの、`1` の個数

明らかに、$DP_s[0]=0,DP_d[0]=1$ である。

また、$1\leq i$ のとき、DPの値は以下のようになる。

* $DP_s[i]=2DP_d[i-1]-1$
* `00` に $1$ 回操作すると `010` になるので、`01` と `10` に対して$i-1$ 回操作を行うことになる。真ん中に挿入した `1` が重複して数えられることに留意。
* $DP_d[i]=DP_s[i-1]+DP_d[i-1]$
* `01` に $1$ 回操作すると `001` になるので、 `00` と `01` に対して $i-1$ 回操作を行うことになる。`10` の場合でもほぼ同様。

DPの様子をある程度手計算してみることにする。

| $i$ | $DP_s[i]$ | $DP_d[i]$ |
| - | - | - |
| $0$ | $0$ | $1$ |
| $1$ | $1$ | $1$ |
| $2$ | $1$ | $2$ |
| $3$ | $3$ | $3$ |
| $4$ | $5$ | $6$ |
| $5$ | $11$ | $11$ |
| $6$ | $21$ | $22$ |
| $7$ | $43$ | $43$ |

こう見ると、$i$ が奇数のとき $DP_s[i]=DP_d[i]$ になりそうである。これを帰納法で証明しておこう。(なお本番中は証明していない)

* $i=1$ のとき、明らかに正しい。
* $3\leq i$ かつ $i$ が奇数のとき、
* $DP_s[i]=2DP_d[i-1]-1=2DP_s[i-2]+2DP_d[i-2]-1$
* $DP_d[i]=DP_s[i-1]+DP_d[i-1]=2DP_d[i-2]-1+DP_s[i-2]+DP_d[i-2]$
* $DP_s[i-2]=DP_d[i-2]$ より、$DP_s[i]=DP_d[i]$

重要なのは $DP_s[2023]$ と $DP_d[2023]$ である。以降、$X=DP_s[2023]=DP_d[2023]$ とする。

基本的に `1` の数は $2022X$ になりそうだが、これらは両端以外の文字を重複して数えているため、その数だけ引かれることになる。

`1` の個数の最大化を考えると、明らかに $2$ 文字目から $2022$ 文字目はすべて `0` にするのがよいことになる。$1$ 文字目と $2023$ 文字目はどちらでもよいので、結局以下の $4$ 通りになる。

* `00000...00000`
* `10000...00000`
* `00000...00001`
* `10000...00001`

これらに対応する文字列は各 $2$ 通りである (最も左の `0` を `A` と `B` のどちらにするかを決めると、その他も一意に定まる) から、$m=8$ である。

また、$M=2022X$ である。

`1` の個数の最小化を考えると、$2$ 文字目から $2022$ 文字目の `1` の個数を最大化すればよいことになる。この区間の長さは奇数なので、`01010...01010` のみに対応する。

`0` の個数は $\lceil \frac{2023}{2}\rceil=1012$ であり、すべての `0` を独立に `A` または `B` に対応させることができるので、これに対応する文字列は $2^{1012}$　通りである。よって、$n=2^{1012}$ である。

また、`1` の個数は $2023-1012=1011$ 個なので、$N=2022X-1011$ である。

$m,n$ が求まったので、あとは $X$ を求めれば、$M,N$ が求まり問題が解ける。

先ほどのDPテーブルの、奇数のところだけを取り出したものを考える。そして、それらを $2$ 進数表記してみる。(だいたい倍々に増えているので規則性がありそうと踏んでいる)

| $i$ | $DP_s[i]$ | $DP_s[i]$ の $2$ 進数表記 |
| - | - | - |
| $1$ | $1$ | $1$ |
| $3$ | $3$ | $11$ |
| $5$ | $11$ | $1011$ |
| $7$ | $43$ | $101011$ |

こうしてみると、どんどん $10$ が増えてきそうな気持ちになる。試しに $i=9$ などを計算してみるとなおさら正しそうである。実際、これは以下のように証明できる。(なおこれも本番中は証明していない)

$DP_s[i]=2DP_d[i-1]-1=2DP_s[i-2]+2DP_d[i-2]-1=4DP_s[i-2]-1$

より、$2$ 進数表記では末尾の $1$ を $0$ にして $11$ を付け加えるといえる。

こうすると、$DP_s[i]=\frac{2^i-2}{3}+1$ と表すことができる。よって、$X=\frac{2^{2023}-2}{3}+1$ となる。

これらの値を $503$ で割った余りを求めよう。以降、$\bmod 503$ を省略する。

Fermatの小定理より、

* $X\equiv \frac{2^{2023}-2}{3}+1\equiv \frac{2^{15}-2}{3}+1\equiv \frac{32766}{3}+1\equiv 10923 \equiv 360$
* $n\equiv 2^{1012}\equiv 2^{8}\equiv 256$

これらより、答えは

$2022X+8+(2022X-1011)+256\equiv 727920+8+726909+256\equiv 1455093\equiv \mathbf{417}$