Codeforces 1119H: Triple
https://codeforces.com/problemset/problem/1119/H
問題概要
が固定されている.
に対して
が与えられるので,
たちを
の指数は XOR で畳み込む,というのを速くやる.
考察
Hadamard 変換すれば畳み込みが掛け算になる (常識) けど,そのままやると長さ の列を
個作らなければいけなくてダメ.
を Hadamard 変換すると
項目は
になる (
は
ビットの整数を長さ
のベクトルと見た内積) (定義).ので,出てくる値は
しかない (これは定義に戻ることを忘れていても実験すればわかる).ので,
項目の積は
みたいになって (
とかは
に依存),
とか関係なくて
個の指数が上手く求まればうれしい.例えば
は
が全部偶数になるような
の個数とかそういう.手早く数えられそうでできない (「数える」という考えから抜けられなくてコンテスト中はここで止まった).
「 とか関係なくて」とか言ったんだから特殊な値を代入して何かしてみるべき (極めて一般的な手法).例えば
として (これは自然な「特殊な値」),
だけど,これすら各
について手早くのは難しそうなうえに得られる情報量が少ない (普通の感想).得られる情報量を多くしようとして指数の底を
とか
とかじゃないようにしても綺麗になる気配はない (たぶん普通の美的感覚).ということで,代わりに
を考えよう (これは,お気持ちはわからなくはないけど,かなり賢いと思う).左辺は Hadamard 変換の線形性を使えるうれしい形をしていて,
を一度変換すれば各
について求まる.
同様に と
が求まることがわかった.あとどんな関係があれば
とかを特定できるか?というと,長さ
の Hadamard 変換っぽい見た目をしているので (Hadamard 変換の問題を解いているのだから Hadamard 変換っぽい見た目には気づく),
とかそういうやつがほしい.それは
とかで,そんなのが求まるかというと,よく見ると
なのでうれしい (冷静さが必要).これでできたのでまとめると,
解法
のそれぞれを Hadamard 変換する.
- 各
に対して,
項目を集めて長さ
の列にして Hadamard 逆変換すると,
の各指数が得られるので,計算する.
- というのを並べて,Hadamard 逆変換すると答え.
コメント
項しかないというのの
は小さいことしか本質ではなくて,
項だったら
時間とかでできますね.
思考の整理のために書いてみたのですが,賢いところが一箇所な割にはすごいことができていて,不思議な感じが残りました.