概要
Atcoderでよくある、分数を剰余であらわすやつがでるたびに和はどうすればよいのか、積はどうすればよいのかを毎回考えてなんとなくやってたので、これを機にまとめようと思います。
理解しているひとからすれば当たり前のことだと思いますが、こうやって考えることを一つずつ減らしてくことは早解きにつながる大切なことだと思います。
(※)剰余については雰囲気で理解しているため、結論について間違っている可能性があります。(コンテストでは通っているので多分あってはいると思うのですが) 間違っていたらご指摘ください。
分数を剰余であらわすやつとは
そもそも、ここでいう「分数を剰余であらわすやつ」とはABC323-Eにあるように\frac{y}{x}をxz \equiv yとなるzであらわすものです。
詳細な定義はAtcoderより以下です。
[確率mod 998244353の定義]
この問題で求める確率は必ず有理数になることが証明できます。 また、この問題の制約下では、求める確率を既約分数 \frac{y}{x}で表したときに xが 998244353 で割り切れないことが保証されます。このとき xz \equiv y(mod 998244353) を満たすような 0 以上 998244352 以下の整数 z が一意に定まります。この z を答えてください。
これについてはよく確率を求める問題ででてきますが、そのたびに和はどうすばよかったっけ？積はどうすればよかったっけ？となっていました。そのため、z同士の計算について本記事で触れようと思います。
分数同士の和と積の計算
\frac{y_1}{x_1}に対して、x_1z_1 \equiv y_1(mod 998244353)であるz_1と、同様に
\frac{y_2}{x_2}に対して、x_2z_2 \equiv y_2(mod 998244353)であるz_2があるとき、
\dfrac{y_1}{x_1}+\dfrac{y_2}{x_2}に対応するz_3を求める方法(和)、
\dfrac{y_1y_2}{x_1x_2}に対応するz_4を求める方法(積)を求めたいと思います。
また、以降の内容では以下の式を証明に使います。
x_1z_1 \equiv y_1(mod 998244353) ... ①
x_2z_2 \equiv y_2(mod 998244353) ... ②
和の計算
結論からいえば、z_3 \equiv z_1+z_2 です。
証明：
\dfrac{y_1}{x_1} + \dfrac{y_2}{x_2} = \dfrac{x_2y_1+x_1y_2}{x_1x_2}より、
(x_1x_2)z_3 \equiv x_2y_1+x_1y_2 ... ③
①, ②, ③より、
(x_1x_2)z_3 \equiv x_2x_1z_1+x_1x_2z_2
よって、
z_3 \equiv z_1+z_2
積の計算
結論からいえば、z_4 \equiv z_1z_2 です。
証明：
\dfrac{x_1}{y_1}\dfrac{x_2}{y_2} = \dfrac{y_1y_2}{x_1x_2} より、
(x_1x_2)z_4 \equiv y_1y_2 ... ④
①, ②, ③より、
(x_1x_2)z_3 \equiv x_1z_1x_2z_2
よって、
z_4 \equiv z_1z_2
結論
結論、分数の和・積の結果に対応するzを求める際も事前に計算してあるz_1, z_2を使って同様に和・積を求めればよい ということですね(間違ってたらすみません)。少し計算してみれば当たり前のことですが、元の計算方法と同様の計算方法でよく、かつ分数を一つの整数で表せるようにしているの改めてすごいですね。
Discussion