ABC348 F - Oddly Similar

8×10^9 の計算量でも、処理がめちゃくちゃシンプルなら間に合う！！！！（だいたい1000ms）

    #[allow(dead_code)]
    fn solve_naive(&self) -> Answer {
        // self.xss.tuple_combinations() でよかった
        let ans = (0..self.n)
            .tuple_combinations()
            .filter(|(i, j)| {
                izip!(&self.xss[*i], &self.xss[*j])
                    .filter(|(x, y)| x == y)
                    .count()
                    % 2
                    == 1
            })
            .count();
        Answer { ans }
    }

O(N^2M) に寄与している部分は filter の x==y の部分と count の部分だけ。

tuple_combinations を使っているから、実はN^2M/2 (4×10^9)回のループになっている。

定数倍最適化テクニック

• i32 が速い（16bit整数は32bit整数より速くない。なぜかむしろ遅い）
  • 実行時間を計測した検証ツイート
  • [Rust] 整数型の四則演算ベンチマーク #Rust - Qiita
• if文を回避すると速い
  • 例: res ^= a[k] == b[k]
  • 投機実行みたいな話と関係あるはず。

bitset による解法

(後で書く)

メモ

• modint の割り算は遅いので、ボトルネックの部分の割り算の回数を減らすと、それだけでだいぶ早くなる。

類題

a^4 + ab + b^4 = C を満たす正整数の組 (a ,b) 全列挙 （1≦C≦10^18）