suisen_kyopro https://blog.hatena.ne.jp/suisen_kyopro/ suisen のブログ https://suisen-kyopro.hatenablog.com/ 問題 atcoder.jp 解法 雑ですが画像だけで伝わってほしい。 問題文の $H,W$ からそれぞれ $1$ ずつ引いて縦の移動回数がちょうど $H$ 回、横の移動回数がちょうど $W$ 回になるよう調整しています。 画像中の「非交差」という表現は不適切かもしれなくて、正確には「始終点以外で同じマスにいることがないようなような移動」です。 補足 $\displaystyle \sum _ {n = 0} ^ \infty \binom{2n}{n} x ^ n = \dfrac{1}{\sqrt{1 - 4x}}$ は、カタラン数の母関数 $\displaystyle \sum _ {n … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fsuisen-kyopro.hatenablog.com%2Fentry%2F2023%2F09%2F22%2F193146" title=" AtCoder Regular Contest 124 F - Chance Meeting - suisen のブログ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.blog.st-hatena.com/images/theme/og-image-1500.png Hatena Blog https://hatena.blog 2023-09-22 19:31:46 rich https://suisen-kyopro.hatenablog.com/entry/2023/09/22/193146 1.0 100%