結果

問題 No.2362 Inversion Number of Mod of Linear
ユーザー akakimidori
提出日時 2025-05-03 11:03:14
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 43 ms / 2,000 ms
コード長 9,409 bytes
コンパイル時間 15,469 ms
コンパイル使用メモリ 378,480 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2025-05-03 11:03:31
合計ジャッジ時間 13,681 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

// sum_{0 <= i < j < N} ceil((A_i - A_j) / M)
//

use std::io::Write;

fn main() {
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    input! {
        t: usize,
        ask: [(usize, usize, usize, usize); t],
    }
    for (n, m, x, y) in ask {
        let dx = GenericFloorSum::<usize, 2, 2>::dx();
        let dy = GenericFloorSum::dy();
        let p = floor_monoid(n, m, x, y, dx.clone(), dy.clone()).flush();
        let q = floor_monoid(n, m, x, 0, dx, dy).flush();
        let ans = 2 * p[1][1] - (n - 1) * p[0][1] - n * q[0][1] + q[1][1];
        writeln!(out, "{}", ans).ok();
    }
}

impl Zero for usize {
    fn zero() -> Self {
        0
    }
    fn is_zero(&self) -> bool {
        *self == 0
    }
}

impl One for usize {
    fn one() -> Self {
        1
    }
    fn is_one(&self) -> bool {
        *self == 1
    }
}

// ---------- begin input macro ----------
// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[macro_export]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

#[macro_export]
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

#[macro_export]
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, bytes) => {
        read_value!($iter, String).bytes().collect::<Vec<u8>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
// ---------- end input macro ----------

// OP=false の時、モノイドではなくなるのに注意
// 基本的に自作のdx dy を使うとかじゃない限りはそのままでいいはず
#[derive(Clone)]
pub struct GenericFloorSum<T, const A: usize, const B: usize, const OP: bool = false> {
    x: [T; A],
    y: [T; B],
    s: [[T; B]; A],
}

impl<T, const A: usize, const B: usize, const OP: bool> GenericFloorSum<T, A, B, OP>
where
    T: SemiRing + Copy,
{
    fn dx() -> Self {
        let mut res = Self::id();
        res.x[1] = T::one();
        res.s[0][0] = T::one();
        res
    }
    fn dy() -> Self {
        let mut res = Self::id();
        res.y[1] = T::one();
        res
    }
    fn flush(&self) -> [[T; B]; A] {
        let mat = floor_flush_matrix::<T, A>();
        let mut ns = [[T::zero(); B]; A];
        for (ns, mat) in ns.iter_mut().zip(mat.iter()) {
            for (s, m) in self.s.iter().zip(mat.iter()) {
                for (ns, s) in ns.iter_mut().zip(s.iter()) {
                    *ns = *ns + *m * *s;
                }
            }
        }
        let mat = floor_flush_matrix::<T, B>();
        let mut s = [[T::zero(); B]; A];
        for (s, ns) in s.iter_mut().zip(ns.iter()) {
            for (s, mat) in s.iter_mut().zip(mat.iter()) {
                for (m, ns) in mat.iter().zip(ns.iter()) {
                    *s = *s + *m * *ns;
                }
            }
        }
        s
    }
}

fn floor_flush_matrix<T, const N: usize>() -> [[T; N]; N]
where
    T: SemiRing + Copy,
{
    let mut res = [[T::zero(); N]; N];
    let mut dp = [T::zero(); N];
    dp[0] = T::one();
    res[0] = dp;
    for i in 1..N {
        let mut next = [T::zero(); N];
        let mut mul = T::one();
        for j in 1..N {
            next[j] = mul * (dp[j - 1] + dp[j]);
            mul = mul + T::one();
        }
        dp = next;
        res[i] = dp;
    }
    res
}

impl<T, const A: usize, const B: usize, const OP: bool> Monoid for GenericFloorSum<T, A, B, OP>
where
    T: SemiRing + Copy,
{
    fn id() -> Self {
        let mut res = Self {
            x: [T::zero(); A],
            y: [T::zero(); B],
            s: [[T::zero(); B]; A],
        };
        res.x[0] = T::one();
        res.y[0] = T::one();
        res
    }
    fn merge(&self, rhs: &Self) -> Self {
        if OP {
            let mut x = [T::zero(); A];
            let mut ns = [[T::zero(); B]; A];
            for (i, a) in self.x.iter().enumerate() {
                for (c, b) in x[i..].iter_mut().zip(rhs.x.iter()) {
                    *c = *c + *a * *b;
                }
                for (ns, b) in ns[i..].iter_mut().zip(rhs.s.iter()) {
                    for (ns, b) in ns.iter_mut().zip(b.iter()) {
                        *ns = *ns + *a * *b;
                    }
                }
            }
            let mut y = [T::zero(); B];
            let mut s = self.s;
            for (i, a) in self.y.iter().enumerate() {
                for (c, b) in y[i..].iter_mut().zip(rhs.y.iter()) {
                    *c = *c + *a * *b;
                }
                for (s, ns) in s.iter_mut().zip(ns.iter()) {
                    for (c, b) in s[i..].iter_mut().zip(ns.iter()) {
                        *c = *c + *a * *b;
                    }
                }
            }
            Self { x, y, s }
        } else {
            let mut x = rhs.x;
            let mut ns = rhs.s;
            for i in 1..A {
                let a = self.x[i];
                for j in i..A {
                    x[j] = x[j] + a * rhs.x[j - i];
                }
                for j in i..A {
                    for k in 0..B {
                        ns[j][k] = ns[j][k] + a * rhs.s[j - i][k];
                    }
                }
            }
            let mut y = rhs.y;
            let mut s = ns;
            for i in 1..B {
                let a = self.y[i];
                for j in i..B {
                    y[j] = y[j] + a * rhs.y[j - i];
                }
                for k in 0..A {
                    for j in i..B {
                        s[k][j] = s[k][j] + a * ns[k][j - i];
                    }
                }
            }
            for i in 0..A {
                for j in 0..B {
                    s[i][j] = s[i][j] + self.s[i][j];
                }
            }
            Self { x, y, s }
        }
    }
}

pub trait Monoid: Clone {
    fn id() -> Self;
    fn merge(&self, rhs: &Self) -> Self;
    fn pow(&self, mut n: usize) -> Self {
        if n == 0 {
            return Self::id();
        }
        if n == 1 {
            return self.clone();
        }
        let mut t = self.clone();
        n -= 1;
        let mut r = self.clone();
        while n > 1 {
            if n & 1 == 1 {
                t = t.merge(&r);
            }
            r = r.merge(&r);
            n >>= 1;
        }
        t.merge(&r)
    }
}

pub fn floor_monoid<T>(
    mut n: usize,
    mut m: usize,
    mut a: usize,
    mut b: usize,
    mut x: T,
    mut y: T,
) -> T
where
    T: Monoid,
{
    let mut front = T::id();
    let mut tail = T::id();
    let mut c = (a * n + b) / m;
    loop {
        if a >= m {
            let q = a / m;
            a %= m;
            x = x.merge(&y.pow(q));
            c -= q * n;
        }
        if b >= m {
            let q = b / m;
            b %= m;
            front = front.merge(&y.pow(q));
            c -= q;
        }
        if c == 0 {
            break;
        }
        let need = (m * c - b + a - 1) / a;
        tail = y.merge(&x.pow(n - need)).merge(&tail);
        n = c - 1;
        c = need;
        b = m - b + a - 1;
        std::mem::swap(&mut a, &mut m);
        std::mem::swap(&mut x, &mut y);
    }
    front.merge(&x.pow(n)).merge(&tail)
}
// ---------- begin trait ----------

use std::ops::*;

pub trait Zero: Sized + Add<Self, Output = Self> {
    fn zero() -> Self;
    fn is_zero(&self) -> bool;
}

pub trait One: Sized + Mul<Self, Output = Self> {
    fn one() -> Self;
    fn is_one(&self) -> bool;
}

pub trait Group: Zero + Sub<Output = Self> + Neg<Output = Self> {}
pub trait SemiRing: Zero + One {}
pub trait Ring: SemiRing + Group {}
pub trait Field: Ring + Div<Output = Self> {}

impl<T> Group for T where T: Zero + Sub<Output = Self> + Neg<Output = Self> {}
impl<T> SemiRing for T where T: Zero + One {}
impl<T> Ring for T where T: SemiRing + Group {}
impl<T> Field for T where T: Ring + Div<Output = Self> {}

pub fn zero<T: Zero>() -> T {
    T::zero()
}

pub fn one<T: One>() -> T {
    T::one()
}

pub fn pow<T: One + Clone>(mut r: T, mut n: usize) -> T {
    let mut t = one();
    while n > 0 {
        if n & 1 == 1 {
            t = t * r.clone();
        }
        r = r.clone() * r;
        n >>= 1;
    }
    t
}

pub fn pow_sum<T: SemiRing + Clone>(r: T, n: usize) -> T {
    if n == 0 {
        T::zero()
    } else if n & 1 == 1 {
        T::one() + r.clone() * pow_sum(r, n - 1)
    } else {
        let a = T::one() + r.clone();
        let b = r.clone() * r;
        a * pow_sum(b, n / 2)
    }
}
// ---------- end trait ----------
0