AtCoder Regular Contest 144

　Cまで三完だが、遅かったためレートを下げた。解いている最中はそれほど遅い気がしなかったのに、順位は悪かったので、（自分では分からなかったが）体調が悪かったのかもしれない。

コンテストへのリンク

コンテスト後のツイート

AtCoder Regular Contest 144 Cまで
A 5以上は繰り上がるから使っちゃダメ
B 二分探索
C iより大きいか小さいかで実験したら規則が見えた
D 実験したらhttps://t.co/CqXGwDE88Sが出てきた。これを使って形式的ベキ級数でいけるのか？　と思ったが慣れてないため分からず終了。

— titia (@titia_til) July 16, 2022

D - AND OR Equation

　解説ACだが、今見返すとチャンスはあった。

　実験してoeis（これやこれなどが出てくる）と見比べれば${(1+x)}^N/{(1-x)}^{(N+2)}$の$K$次の係数と分かる。

・${(1+x)}^N$は、二項定理を使って展開

・${(1-x)}^{(N+2)}$は、$1/(1-x)=1+x+x^2+x^3+...$とできることを利用すると重複組み合わせにより二項係数になる

　を利用すれば求められる。

　ただし、二項係数を求めるとき、Kが998244353に近い値のときは気をつけて計算しなくてはいけない。（コンテスト中に、ここの処理まで上手くできた可能性はかなり低そう……）

　コンテスト中、形式的冪級数で表すところまではできていて、その後は多少技巧的ではあるが自分で思いつける変形だった。

　特に一番目、二項定理を使おうとも考えなかったのはひどい。形式的冪級数を使うならここは押さえねば。