ですね。

クイズです。$p/q\equiv 709787742\pmod{998244353}$ を満たす互いに素な正整数のペアはなんでしょうか。

答えは $(p,q)=(25,30233088)$ です。 $(p,q)=(23583,26948)$ だと思った人もいるかもしれませんが、サイコロを $10$ 回だけ振ってちょうど $9$ 回だけ $1$ の目が出る確率 $\pmod{998244353}$ を想定していたので、ちがいます（ちがいはしませんけど）。¹

こんなふうに、競技プログラミングの問題を解いていて出てくるおおきめ有理数 $\pmod p$ の値からもとのおおきめ有理数がわかると、サンプルがわかりやすくなったりどこで壊れているのか確認しやすくてうれしいですね。知る方法について書きます。

元ネタ？はこちらです。いっしょにどうぞ？

rsk0315.hatenablog.com

主に C++ で競技プログラミングをしている人に向けて書いています。別の言語でプレイしている人がどういう感じになるのかはわかりません。ぽか

まとめ

最初から有理数で計算してしまえばいいですね。

日記要素ですか？

ちがいます。

まじめなはなし

modint などを使って dp をしたりするとき、boost::rational や long double と併用したり切り替えたりできると、サンプルを試してみたときに「なんだか逆数を求めていた」とか、「なんだか確率じゃなくて期待値を計算していた」みたいなミスに気づきやすそうですね。

わたしはこんなときには main 関数の頭に

int main(){
    using modint = atcoder::static_modint<998244353>; // ふつうの modint です
//    using modint = boost::rational<boost::multiprecision::cpp_int>; // 有理数です
//    using modint = long double; // 浮動小数点数です

のように型エイリアスをおいています。これのコメントをつけはずししながらサンプルを実行してみてデバッグをしているというわけですね。この型エイリアスの名前が modint なのはどうかと思ってたまに dp_value_type とか ans_type みたいにすることもあるんですけど、結局戻ってきてしまっています。コメントつけはずしなのもどうかと思ってたまに template<typename modint> みたいにした solve 関数を書くこともあるんですけど、結局戻ってきてしまっています。もうちょっといい名前とか便利な切り替え方法をご存知の方はおしらせください。

きをつけていること

raw とか pow とか inv とか、上の 3 つのうち atcoder::static_modint にしかないものを使っているとコンパイルエラーになりがちです。使わないようにするか、もう 2 つについても同じ名前の関数を作ってしまうことでなんとかなるかもしれません。抽象化した関数を作ってあげて関数の中でこれらの違いを吸収してあげてもいいかもしれないですね。 val は入出力の operator<<(std::ostream&, modint) みたいなのをつくっておくほうがおきにいりです。

また、boost::rational<boost::multiprecision::cpp_int> を使っているときに、適当に計算した結果を auto で受けたりすると型が変になったりすることがあるので、modint で受けていい感じにしておくことがだいじかもしれません。

またまた、boost::rational<boost::multiprecision::cpp_int> で分子や分母の値がおおきくなっていくと、遅くなります。こういうときはあきらめて long double などを使いましょう。

atcoder.jp

たとえばこういうときですね。$10 ^ 8$ 桁くらいになりそうな感じがします。ならないかも。