ABC#024の戦績

A,B,CがACで300点、順位的には100位というキリ番。やっぱりコンテストになると若干焦ってコードが雑だったりコーナーケースを逃したりするので場慣れしたい。

A.

　場合分けするぐらいで特に言うことはない。

B.

　まあ見るからにいもす法なのでそのまま組む。始点と終点の設定を若干しくってしまったのでちょい時間ロス。

C.

　これはちょっと考察した。移動の仕方は法則があるのかとか考えたけど、考えるうちに安直なことに気づいてgreedy。ここまでで45分ぐらい。

D.

　動的計画法って書いてるけどどう考えてもメモリも時間も足りない。O(N^2)だけどO(NlogN)とかにへらすなら行列にしてダブリングかと思ったけど行列がそもそもN^3だし無理だ。というわけでやっぱり代数的にO(1)かなって思う。

　ごりごり数式をいじって二元連立方程式になり解いた。けど当然割り算がでてくる。合同式で割り算てまずいんじゃねっけって思考停止。諦め。

//Dの解法

解法はやっぱり代数的な解き方。問題は合同式での割り算。

合同式での割り算は条件を満たせばできる。ただし逆元をかけるという方式を使う。逆元というのはXY=1(mod p)となるYのこと。これば実数でいえば1/xだったりする。合同式ではどうかというとmod素数なら簡単に求まる。

フェルマーの小定理というのがあってaと素数pが互いに素であるとき

a^(p-1)=1 (mod p)

がなりたつ。これよりaの逆元はa^(p-2)となる。今回は10^9+7で素数なのでこれが利用できる。

　でもp乗って10^9+7じゃん...

これはまあ察しがつくようにダブリングをすればいい。これでO(logN)となって問題解決。

あとはプログラムをかくだけ。...だったのだが入力をintにしていたためオーバーフロー。

10億7の問題ではlong longを使いましょう。ってオチ