AtCoder Beginner Contest 009:D - 漸化式
問題
https://atcoder.jp/contests/abc009/tasks/abc009_4
考え方
難しい。半環上に定義される演算は行列の演算と同じことができる。フィボナッチ数列を行列で表すと以下のようになる。
これと同様の考え方でビット演算のANDとXORをANDは 、XORは に対応させることができる。単位元は Long.MAX_VALUE
として
である。そのように考えると問題で与えられた操作は行列で定義できて、また第 項はフィボナッチ数列と同様の考え方で求めることができる。よって行列累乗で で第 項を求めることができる。
どこに着目して考察するべきだったか
半環の演算に着目する。操作を行列で表すことで行列累乗が適応できる形になる。
何がバグっていたか
得た知見(典型ポイント)
- 半環の演算に落とし込む