リンク
問題 https://abc042.contest.atcoder.jp/
解説 http://arc058.contest.atcoder.jp/data/arc/058/editorial.pdf
今回から新形式になっている。
概要
A, Bはやるだけ。
Cは繰り上がりなどを巧妙に考えたやや長いコードで通したが、全探索でいけるらしい旨が解説されている。
Dは解説があまりに不親切だが「フェルマーの小定理より $(x!)^{−1} \equiv x^{10^9+5} (\text{mod }10^9 + 7)$ である。」とのこと。全く意味がわからないがこれを一瞬で思いつけるかどうかで解けるかどうかが決まるらしい。数え上げの方法も非自明だと思うが、とくに説明がないので誰でも簡単にわかるようだ。天才たちのゲームはむずかしい。
Beginner Contestを名乗っておきながら初心者のためになるものを作る気がない感を隠さないのはいかがか。
フェルマーの小定理とは、平たく言うと、$p$ が素数、$a$ が $p$ と互いに素な整数としたときに $a$ の $p - 1$ 乗を $p$ で割った余りは $1$ になるということを述べたもの。
$10^9 + 7$ は素数である。またこのことから $2$ 以上 $10^9 + 7$ 未満の整数 $x$ はいずれも $10^9 + 7$ と互いに素であることが分かるし、更にそのことから $x!$ も同じく $10^9 + 7$ と互いに素になることが分かる（$10^9 + 7$ と互いに素な整数のみを掛けあわせた結果であることから）。
つまりフェルマーの小定理を使って $2$ 以上 $10^9 + 7$ 未満の整数 $x$ に対して $(x!)^{10^9 + 7 - 1} \equiv 1 (\text{mod }10^9 + 7)$ 、すなわち $(x!)^{-1} \equiv (x!)^{10^9 + 7 - 2}$ となることが分かる。
これで右辺がただの正数による累乗になって式変形が簡単になり、
\[\begin{eqnarray*}
(x!)^{-1} &\equiv& (x!)^{10^9 + 7 - 2} \\
&\equiv& ((x - 1)!)^{10^9 + 7 - 2} \times x^{10^9 + 7 - 2} \\
&\equiv& ((x - 1)!)^{-1} \times x^{10^9 + 7 - 2}
\end{eqnarray*}\]
てな感じで漸化式っぽく簡単に計算できそうになった。
…………あれ、解説とちがうなあ。
関係無いけどMathJaxを導入した。
やり方は http://irrep.blogspot.jp/2011/07/mathjax-in-blogger-ii.html に従っただけ。
更に関係無いけど：
このあともうちょっとアホな部分をまともに書きなおしたらPython3でも通った。
$(x!)^{-1}$ を事前計算しておくのを逆順に計算すると簡単。
と、思ったけどPythonにはpow(x, y, z)があるのでそんなことしなくてもいいのか。
Cは繰り上がりなどを巧妙に考えたやや長いコードで通したが、全探索でいけるらしい旨が解説されている。
Dは解説があまりに不親切だが「フェルマーの小定理より $(x!)^{−1} \equiv x^{10^9+5} (\text{mod }10^9 + 7)$ である。」とのこと。全く意味がわからないがこれを一瞬で思いつけるかどうかで解けるかどうかが決まるらしい。数え上げの方法も非自明だと思うが、とくに説明がないので誰でも簡単にわかるようだ。天才たちのゲームはむずかしい。
Beginner Contestを名乗っておきながら初心者のためになるものを作る気がない感を隠さないのはいかがか。
フェルマーの小定理とは、平たく言うと、$p$ が素数、$a$ が $p$ と互いに素な整数としたときに $a$ の $p - 1$ 乗を $p$ で割った余りは $1$ になるということを述べたもの。
$10^9 + 7$ は素数である。またこのことから $2$ 以上 $10^9 + 7$ 未満の整数 $x$ はいずれも $10^9 + 7$ と互いに素であることが分かるし、更にそのことから $x!$ も同じく $10^9 + 7$ と互いに素になることが分かる（$10^9 + 7$ と互いに素な整数のみを掛けあわせた結果であることから）。
つまりフェルマーの小定理を使って $2$ 以上 $10^9 + 7$ 未満の整数 $x$ に対して $(x!)^{10^9 + 7 - 1} \equiv 1 (\text{mod }10^9 + 7)$ 、すなわち $(x!)^{-1} \equiv (x!)^{10^9 + 7 - 2}$ となることが分かる。
これで右辺がただの正数による累乗になって式変形が簡単になり、
\[\begin{eqnarray*}
(x!)^{-1} &\equiv& (x!)^{10^9 + 7 - 2} \\
&\equiv& ((x - 1)!)^{10^9 + 7 - 2} \times x^{10^9 + 7 - 2} \\
&\equiv& ((x - 1)!)^{-1} \times x^{10^9 + 7 - 2}
\end{eqnarray*}\]
てな感じで漸化式っぽく簡単に計算できそうになった。
…………あれ、解説とちがうなあ。
関係無いけどMathJaxを導入した。
やり方は http://irrep.blogspot.jp/2011/07/mathjax-in-blogger-ii.html に従っただけ。
更に関係無いけど：
このあともうちょっとアホな部分をまともに書きなおしたらPython3でも通った。
$(x!)^{-1}$ を事前計算しておくのを逆順に計算すると簡単。
と、思ったけどPythonにはpow(x, y, z)があるのでそんなことしなくてもいいのか。
0 件のコメント:
コメントを投稿