1/23 日記
今日はコンテストもあったけど、あまり集中できていなかった。
バチャを積極的にやっていって集中しようとする時間を増やそうかと思う。
Mが大きいため、A(M)を求めるには何かしらの高速化が必要になる
①ビットごとにみるのはどうか→周期が見えそうな数列ではないため厳しい
➁行列累乗は使えないか→これが上手くいく。単位行列の対角成分はandを取った時に値が変わらないようにする必要があるから、1LL<<32-1としておく。普通の行列累乗をやるときの要素の掛け算がandに、足し算がxorに対応する。
各i ( 1~N )について、A[i]を使わないときのK未満の値の最大値を求められればいい。
普通にdpしようとするとO(N^2K)かかってしまう。ここで、左からのdplと右からのdprをそれぞれ求めておくことで、K未満の値の最大値を高速に求められる。
dplとdprのマージは、それぞれの最大値がKであることからO(K)で可能。
・E - Rotate and Flip (atcoder.jp)
今日のABC。各操作は単純なので、初期位置が与えられたときに各操作後の座標を高速に求められるようにしたいと考えると行列計算みたいのが思いつく（他の方法でも可）。行列計算のとき、初期位置をp=(X, Y)、2×2行列A、2次元ベクトルcを考えると、現在の座標はnow=Ap+cと求めることができる。
つまり、各操作後のA、cを更新していけばいい。
このときに行列の掛け算の順番に注意()。
ABC-Fは明日考える。
ぷらにゃが可愛すぎるね。好き好き
