Chebyshev Cafe の解説

$$\max(|x|, |y|) = \frac{|x + y| + |x - y|}{2}$$

なので、カフェ(i, j)に(r, c)に住んでる住人が移動するコストは

$$\max(|i - r|, |j - c|) = \frac{|(i + j) - (r + c)| + |(i - j) - (r - c)|}{2}$$

になる。

よって、集合場所(i, j)を固定した時の全体コストは(r, c)にいる住民の数をC_rcとすると

$$\sum_{r,c} C_{r,c} \frac{|(i + j) - (r + c)| + |(i - j) - (r - c)|}{2}$$

となる。

左側だけ考える。

$$\sum_{r,c} C_{r,c} |(i + j) - (r + c)|$$

(r + c) = kとなる住民の数の総和をukとしたら、

$$\sum_k u_k |(i + j) - k|$$

と変形できる。

(i, j)固定してるので、絶対値は固定した値によって外すことができ、

$u_k$, $ku_k$の累積和をとっておけば高速に計算可能。

右側もほとんど同様の議論ができるので高速に計算できて解けました。

fn main() {
    input! {
        n: usize, m: isize,
        a: [isize; n],
        b: [isize; n]
    }
    let c = {
        let mut table = vec![];
        for i in 0..n {
            let mut v = vec![];
            for j in 0..n {
                v.push(a[i] * b[j] % m);
            }
            table.push(v);
        }
        table
    };
    let con = |num: isize| (num + n as isize) as usize;
    let (u, ku, um, kum) = {
        let mut u = vec![0; 2 * n];
        let mut um = vec![0; 2 * n];
        for i in 0..n {
            for j in 0..n {
                u[i + j] += c[i][j];
                um[con(i as isize - j as isize)] += c[i][j];
            }
        }
        let mut ku = vec![];
        let mut kum = vec![];
        for k in 0..2 * n {
            ku.push(k as isize * u[k]);
            kum.push((k as isize - n as isize) * um[k]);
        }
        (
            PrefixSum1D::new(&u),
            PrefixSum1D::new(&ku),
            PrefixSum1D::new(&um),
            PrefixSum1D::new(&kum),
        )
    };

    let mut ans = 0;
    for (i, j) in iproduct!(0..n as isize, 0..n as isize) {
        let a = i + j;
        let left = u.range_sum(..=a as usize);
        let right = ku.range_sum(..=a as usize);

        let al = a * left - right;
        let left = ku.range_sum(a as usize..);
        let right = u.range_sum(a as usize..);
        let ar = left - a * right;

        let ans1 = al + ar;
        let ans1 = ans1;

        let a = i as isize - j as isize;
        let left = um.range_sum(..=con(a));
        let right = kum.range_sum(..=con(a));
        let al = a * left - right;
        let left = kum.range_sum(con(a)..);
        let right = um.range_sum(con(a)..);
        let ar = left - a * right;
        let ans2 = al + ar;
        let ans2 = ans2;

        let cur = (ans1 + ans2) / 2 + (i * n as isize) + j;
        ans ^= cur;
    }
    println!("{}", ans);
}