| A | B | C | D | E |
| F | G | H | I | J |
| K | L | M | N | O |
| P | Q | R | S | T |
| U | V | W | X |
以下の条件を全て満たす非負整数の組 $(a,b,c,d)$ を数え上げよ。 ${\rm mod}$ $998244353$
- $a+b+c+d=N$
- $a \in \{0,1\}$
- $b \in \{0,1,2\}$
- $c$ は偶数
- $d$ は $3$ の倍数
$0 \le N \le 10^9$
本番解法: $f(x)$ を以下の条件を満たす非負整数の組 $(c,d)$ の個数とする。
- $c+d=x$
- $c$ は偶数
- $d$ は $3$ の倍数
実験エスパーすると次のコードで求まるらしい。
あとは $a,b$ を全通り探索すれば ok
https://atcoder.jp/contests/fps-24/submissions/70656739
これもまぁオーバーキル気味らしい。実験エスパーも入ってますからね…
欲しいものは次の通り。
$[x^N] (x+1)(x^2+x+1)(1+x^2+x^4+\dots)(1+x^3+x^6+\dots)$
無限和が入っているのでなんとかしようとする。無限等比数列の公式をそのまま使ってよい。
$(1+x^2+x^4+\dots) = \frac{1}{(1-x^2)}=\frac{1}{(1-x)(1+x)}$
$(1+x^3+x^6+\dots) = \frac{1}{(1-x^3)}=\frac{1}{(1-x)(1+x+x^2)}$
因数分解して筋良になるかもというのは A問題 でも扱いましたね。
積を計算すると
$[x^N] \frac{(x+1)(x^2+x+1)}{(1-x)(1+x)(1-x)(1+x+x^2)}$
$=[x^N] \frac{1}{(1-x)^2}$
公式解説 ではここから公式を利用していますが、この記事ではもうちょっと詰めてみましょう。
$[x^N] \frac{1}{(1-x)} \times \frac{1}{(1-x)}$
無限和の形に戻して
$[x^N] (1+x+x^2+\dots) \times (1+x+x^2+\dots)$
$x^N$ の項の係数は左から $x^k$ 、右から $x^{N-k}$ を選んだ $(0 \le k \le N)$ パターンの和と一致するので、欲しい値が $N+1$ であることが分かる。
まぁここから公式解説での公式も直ちに得られますね。
https://atcoder.jp/contests/fps-24/submissions/70717927
B まさかのギャグで仰天。でも FPS 知らないとギャグがギャグであるとも見抜けない可能性があるんだなぁ...
本番解法の $f$ のくだりも FPS で楽に出たりするのかなぁ
自分が証明しろと言われると、 $2x+3y=N$ の非負整数解の個数みたいな話になるので $x$ の範囲を求めて $(+3,-2)$ でずらせてどうたらみたいな感じで証明しそう。
最後のところは 1/(1-x^2)(1-x^3) = (1+x^2+x^3+x^4+x^5+x^7)/(1-x^6)^2 からわかると思います
— SSRS (@SSRS_cp) 2025年11月6日
$\frac{1}{(1-x^2)} = \frac{(1+x^2+x^4)}{(1-x^6)}$
$\frac{1}{(1-x^3)} = \frac{(1+x^3)}{(1-x^6)}$
と分母を揃えて分子は分子同士の積で得る、なるほど。慣れればむっちゃ楽そう。
