がべーじこれくしょん

技術系とかいろいろ

8/20日報

帰省から帰ってきました。揺れる車内で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は素数

フェルマーの小定理より、pが素数のとき、

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)

やっと色がつきました。この調子で頑張りたいです。細かいミスをなくしたい。