baitop https://blog.hatena.ne.jp/baitop/ バイトの競プロメモ https://baitop.hatenadiary.jp/ 問題概略 長さKの数列A,Cが与えられる。 n >= 1で An+k = (c1 & An+k-1) xor (c2 & An+k-2) xor .....(ck & An)である時、 Amを求めよ制約 M N A &とxorが*,+なら行列のべき乗の形にして高速に解ける。 実は今回も同様に出来る。 32ビットの非負の数は&,xor上で半環であり、単位元や交換法則が成り立つので。 単位元には~0Lを使えば良い public static void solve() throws Exception { //longを忘れるなオーバーフローするぞ K = ni(); M = ni(); A = n… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbaitop.hatenadiary.jp%2Fentry%2F2018%2F08%2F24%2F170430" title="D - 漸化式　AtCoder Beginner Contest 009 - バイトの競プロメモ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2018-08-24 17:04:30 rich https://baitop.hatenadiary.jp/entry/2018/08/24/170430 1.0 100%