帰省から帰ってきました。揺れる車内でOS本読んでたら酔ってしまいました。
車酔いはしない体質だったのですが…しばらく自家用車に乗らずに電車に乗ってたせいでしょうか。
1日1AC
ABC071でした。
なんと109 * 109をintでやろうとするという珍プレイを犯してしまい、Cで3WAとかいう大失態をしでかしました。反省はしてません(してます)
All Submissions - AtCoder Beginner Contest 071
Dは全くわからなかったので手をつけませんでした。
Dの
このような塗り方が何通りあるかを mod 1000000007 で求めてください.
という部分の意味がさっぱりわかりませんでした。検索すると以下のような文献が。
www.slideshare.net
普通にmodで割って余りを求めてしまうのは不可能。
そこで、「逆元」を求める。
mod = 1000000007は素数
↓
ap-1 ≡ 1 (mod p) ap-2 ≡ a^-1 (mod p)
つまり、Aで割りたいときは、AのM-2乗をかければよい。
(ab (mod p)の計算は、log bでできるらしい。)
ab(mod p) : aのb乗をpで割った余り
int calc(int a, int b, int p){ if(b==0) return 1; else if(b%2==0) { int d = calc(a, b/2, p); return (d * d) % p; //bが半分にできる } else return (a * calc(a, b-1, p)) % p; }
奇数の後は、偶数が必ず呼ばれるため、2回に1回はbが半分になる。
ゆえに、計算量はO(logb) ということらしいです。
ふむ。次は解けるようになりたい…
382 -> 477 (+95)
やっと色がつきました。この調子で頑張りたいです。細かいミスをなくしたい。