QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#636073#9451. Expected Waiting Timeucup-team296#AC ✓823ms86728kbRust25.9kb2024-10-12 22:05:272024-10-12 22:05:28

Judging History

你现在查看的是最新测评结果

  • [2024-10-12 22:05:28]
  • 评测
  • 测评结果:AC
  • 用时:823ms
  • 内存:86728kb
  • [2024-10-12 22:05:27]
  • 提交

answer

// 
pub mod solution {
//{"name":"b","group":"Manual","url":"","interactive":false,"timeLimit":2000,"tests":[{"input":"","output":""}],"testType":"single","input":{"type":"stdin","fileName":null,"pattern":null},"output":{"type":"stdout","fileName":null,"pattern":null},"languages":{"java":{"taskClass":"b"}}}

#[allow(unused)]
use crate::dbg;
use crate::algo_lib::io::input::Input;
use crate::algo_lib::io::output::Output;
use crate::algo_lib::math::modulo_runtime::ModRuntime;
use crate::algo_lib::misc::num_traits::HasConstants;

type Mod = ModRuntime;

pub fn gen_facts(n: usize, p: i32) -> Vec<Mod> {
    let mut res = Vec::with_capacity(n);
    res.push(Mod::new(1, p));
    for x in 1..=n {
        let num = Mod::new(x as i32, p);
        res.push(*res.last().unwrap() * num);
    }
    res
}

pub struct CombinationsFact {
    fact: Vec<Mod>,
    fact_inv: Vec<Mod>,
    invs: Vec<Mod>,
    p: i32,
}

impl CombinationsFact {
    #[allow(unused)]
    pub fn new(n: usize, p: i32) -> Self {
        let fact = gen_facts(n, p);
        let mut fact_inv = fact.clone();
        assert_eq!(fact_inv.len(), n + 1);
        fact_inv[n] = Mod::new(1, p) / fact_inv[n];
        for i in (1..n).rev() {
            fact_inv[i] = fact_inv[i + 1] * Mod::new((i + 1) as i32, p);
        }
        let mut invs = fact_inv.clone();
        for i in 1..=n {
            invs[i] *= fact[i - 1];
        }
        Self {
            fact,
            fact_inv,
            p,
            invs,
        }
    }

    pub fn fact(&self, n: usize) -> Mod {
        self.fact[n]
    }

    fn c(&self, n: usize, k: usize) -> Mod {
        if k > n {
            return Mod::new(0, self.p);
        }
        self.fact[n] * self.fact_inv[k] * self.fact_inv[n - k]
    }
}

fn solve(input: &mut Input, out: &mut Output, _test_case: usize) {
    let tc = input.usize();
    for _ in 0..tc {
        let n = input.usize();
        let p = input.i32();
        let mut b = ModRuntime::new(input.i32(), p);
        let A = ModRuntime::new(input.i32(), p);
        let B = ModRuntime::new(input.i32(), p);
        let mut a = vec![ModRuntime::new(0, p)];
        for i in 1..=2 * n {
            let a_last = *a.last().unwrap();
            b = A * b + B;
            a.push(a_last + ModRuntime::new(1, p) + b);
        }
        for i in 1..a.len() {
            let prev = a[i - 1];
            a[i] += prev;
        }
        let cnk = CombinationsFact::new(n * 2 + 2, p);
        let mut brackets = vec![Mod::new(1, p); n + 1];
        for i in 1..=n {
            // TODO: slow?
            brackets[i] = cnk.c(i * 2, i) * cnk.invs[i + 1];
        }
        let total_ways = brackets[n];
        let mut res = Mod::new(0, p);
        for k in 1..=n {
            let ways = brackets[k - 1] * brackets[n - k];
            let sz = k * 2;
            let cnt = 2 * n - (sz - 1);
            let sum_right = a[2 * n] - a[sz - 1];
            let sum_left = a[cnt] - a[0];
            let sum_dist = sum_right - sum_left;
            res += ways * sum_dist;
        }
        res /= total_ways;
        out.println(res);
    }
}

pub(crate) fn run(mut input: Input, mut output: Output) -> bool {
    solve(&mut input, &mut output, 1);
    output.flush();
    true
}

}
pub mod algo_lib {
pub mod collections {
pub mod last_exn {
use std::collections::BTreeSet;

pub trait LastExn<T> {
    fn last_exn(&self) -> &T;
}

impl<T> LastExn<T> for &[T] {
    fn last_exn(&self) -> &T {
        self.last().unwrap()
    }
}

impl<T> LastExn<T> for Vec<T> {
    fn last_exn(&self) -> &T {
        self.last().unwrap()
    }
}

impl<T> LastExn<T> for BTreeSet<T> {
    fn last_exn(&self) -> &T {
        self.iter().next_back().unwrap()
    }
}
}
}
pub mod io {
pub mod input {
use std::fmt::Debug;
use std::io::Read;
use std::marker::PhantomData;
use std::path::Path;
use std::str::FromStr;

pub struct Input {
    input: Box<dyn Read>,
    buf: Vec<u8>,
    at: usize,
    buf_read: usize,
}

macro_rules! read_integer_fun {
    ($t:ident) => {
        #[allow(unused)]
        pub fn $t(&mut self) -> $t {
            self.read_integer()
        }
    };
}

impl Input {
    const DEFAULT_BUF_SIZE: usize = 4096;

    ///
    /// Using with stdin:
    /// ```no_run
    /// use algo_lib::io::input::Input;
    /// let stdin = std::io::stdin();
    /// let input = Input::new(Box::new(stdin));
    /// ```
    ///
    /// For read files use ``new_file`` instead.
    ///
    ///
    pub fn new(input: Box<dyn Read>) -> Self {
        Self {
            input,
            buf: vec![0; Self::DEFAULT_BUF_SIZE],
            at: 0,
            buf_read: 0,
        }
    }

    pub fn new_stdin() -> Self {
        let stdin = std::io::stdin();
        Self::new(Box::new(stdin))
    }

    pub fn new_file<P: AsRef<Path>>(path: P) -> Self {
        let file = std::fs::File::open(&path)
            .unwrap_or_else(|_| panic!("Can't open file: {:?}", path.as_ref().as_os_str()));
        Self::new(Box::new(file))
    }

    pub fn new_with_size(input: Box<dyn Read>, buf_size: usize) -> Self {
        Self {
            input,
            buf: vec![0; buf_size],
            at: 0,
            buf_read: 0,
        }
    }

    pub fn new_file_with_size<P: AsRef<Path>>(path: P, buf_size: usize) -> Self {
        let file = std::fs::File::open(&path)
            .unwrap_or_else(|_| panic!("Can't open file: {:?}", path.as_ref().as_os_str()));
        Self::new_with_size(Box::new(file), buf_size)
    }

    pub fn get(&mut self) -> Option<u8> {
        if self.refill_buffer() {
            let res = self.buf[self.at];
            self.at += 1;
            Some(res)
        } else {
            None
        }
    }

    pub fn peek(&mut self) -> Option<u8> {
        if self.refill_buffer() {
            Some(self.buf[self.at])
        } else {
            None
        }
    }

    pub fn skip_whitespace(&mut self) {
        while let Some(b) = self.peek() {
            if !char::from(b).is_whitespace() {
                return;
            }
            self.get();
        }
    }

    pub fn next_token(&mut self) -> Option<Vec<u8>> {
        self.skip_whitespace();
        let mut res = Vec::new();
        while let Some(c) = self.get() {
            if char::from(c).is_whitespace() {
                break;
            }
            res.push(c);
        }
        if res.is_empty() {
            None
        } else {
            Some(res)
        }
    }

    //noinspection RsSelfConvention
    pub fn is_exhausted(&mut self) -> bool {
        self.peek().is_none()
    }

    pub fn has_more_elements(&mut self) -> bool {
        !self.is_exhausted()
    }

    pub fn read<T: Readable>(&mut self) -> T {
        T::read(self)
    }

    pub fn vec<T: Readable>(&mut self, size: usize) -> Vec<T> {
        let mut res = Vec::with_capacity(size);
        for _ in 0usize..size {
            res.push(self.read());
        }
        res
    }

    pub fn string_vec(&mut self, size: usize) -> Vec<Vec<u8>> {
        let mut res = Vec::with_capacity(size);
        for _ in 0usize..size {
            res.push(self.string());
        }
        res
    }

    pub fn read_line(&mut self) -> String {
        let mut res = String::new();
        while let Some(c) = self.get() {
            if c == b'\n' {
                break;
            }
            if c == b'\r' {
                if self.peek() == Some(b'\n') {
                    self.get();
                }
                break;
            }
            res.push(c.into());
        }
        res
    }

    #[allow(clippy::should_implement_trait)]
    pub fn into_iter<T: Readable>(self) -> InputIterator<T> {
        InputIterator {
            input: self,
            phantom: Default::default(),
        }
    }

    fn read_integer<T: FromStr + Debug>(&mut self) -> T
    where
        <T as FromStr>::Err: Debug,
    {
        let res = self.read_string();
        res.parse::<T>().unwrap()
    }

    fn read_string(&mut self) -> String {
        match self.next_token() {
            None => {
                panic!("Input exhausted");
            }
            Some(res) => unsafe { String::from_utf8_unchecked(res) },
        }
    }

    pub fn string_as_string(&mut self) -> String {
        self.read_string()
    }

    pub fn string(&mut self) -> Vec<u8> {
        self.read_string().into_bytes()
    }

    fn read_char(&mut self) -> char {
        self.skip_whitespace();
        self.get().unwrap().into()
    }

    fn read_float(&mut self) -> f64 {
        self.read_string().parse().unwrap()
    }

    pub fn f64(&mut self) -> f64 {
        self.read_float()
    }

    fn refill_buffer(&mut self) -> bool {
        if self.at == self.buf_read {
            self.at = 0;
            self.buf_read = self.input.read(&mut self.buf).unwrap();
            self.buf_read != 0
        } else {
            true
        }
    }

    read_integer_fun!(i32);
    read_integer_fun!(i64);
    read_integer_fun!(i128);
    read_integer_fun!(u32);
    read_integer_fun!(u64);
    read_integer_fun!(usize);
}

pub trait Readable {
    fn read(input: &mut Input) -> Self;
}

impl Readable for String {
    fn read(input: &mut Input) -> Self {
        input.read_string()
    }
}

impl Readable for char {
    fn read(input: &mut Input) -> Self {
        input.read_char()
    }
}

impl Readable for f64 {
    fn read(input: &mut Input) -> Self {
        input.read_string().parse().unwrap()
    }
}

impl Readable for f32 {
    fn read(input: &mut Input) -> Self {
        input.read_string().parse().unwrap()
    }
}

impl<T: Readable> Readable for Vec<T> {
    fn read(input: &mut Input) -> Self {
        let size = input.read();
        input.vec(size)
    }
}

pub struct InputIterator<T: Readable> {
    input: Input,
    phantom: PhantomData<T>,
}

impl<T: Readable> Iterator for InputIterator<T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        self.input.skip_whitespace();
        self.input.peek().map(|_| self.input.read())
    }
}

macro_rules! read_integer {
    ($t:ident) => {
        impl Readable for $t {
            fn read(input: &mut Input) -> Self {
                input.read_integer()
            }
        }
    };
}

read_integer!(i8);
read_integer!(i16);
read_integer!(i32);
read_integer!(i64);
read_integer!(i128);
read_integer!(isize);
read_integer!(u8);
read_integer!(u16);
read_integer!(u32);
read_integer!(u64);
read_integer!(u128);
read_integer!(usize);
}
pub mod output {
use std::io::Write;

pub struct Output {
    output: Box<dyn Write>,
    buf: Vec<u8>,
    at: usize,
    auto_flush: bool,
}

impl Output {
    const DEFAULT_BUF_SIZE: usize = 4096;

    pub fn new(output: Box<dyn Write>) -> Self {
        Self {
            output,
            buf: vec![0; Self::DEFAULT_BUF_SIZE],
            at: 0,
            auto_flush: false,
        }
    }

    pub fn new_stdout() -> Self {
        let stdout = std::io::stdout();
        Self::new(Box::new(stdout))
    }

    pub fn new_file(path: impl AsRef<std::path::Path>) -> Self {
        let file = std::fs::File::create(path).unwrap();
        Self::new(Box::new(file))
    }

    pub fn new_with_auto_flush(output: Box<dyn Write>) -> Self {
        Self {
            output,
            buf: vec![0; Self::DEFAULT_BUF_SIZE],
            at: 0,
            auto_flush: true,
        }
    }

    pub fn flush(&mut self) {
        if self.at != 0 {
            self.output.write_all(&self.buf[..self.at]).unwrap();
            self.at = 0;
            self.output.flush().expect("Couldn't flush output");
        }
    }

    pub fn print<T: Writable>(&mut self, s: T) {
        s.write(self);
    }

    pub fn println<T: Writable>(&mut self, s: T) {
        s.write(self);
        self.put(b'\n');
    }

    pub fn put(&mut self, b: u8) {
        self.buf[self.at] = b;
        self.at += 1;
        if self.at == self.buf.len() {
            self.flush();
        }
    }

    pub fn maybe_flush(&mut self) {
        if self.auto_flush {
            self.flush();
        }
    }

    pub fn print_per_line<T: Writable>(&mut self, arg: &[T]) {
        for i in arg {
            i.write(self);
            self.put(b'\n');
        }
    }

    pub fn print_iter<T: Writable, I: Iterator<Item = T>>(&mut self, iter: I) {
        let mut first = true;
        for e in iter {
            if first {
                first = false;
            } else {
                self.put(b' ');
            }
            e.write(self);
        }
    }

    pub fn print_iter_ref<'a, T: 'a + Writable, I: Iterator<Item = &'a T>>(&mut self, iter: I) {
        let mut first = true;
        for e in iter {
            if first {
                first = false;
            } else {
                self.put(b' ');
            }
            e.write(self);
        }
    }
}

impl Write for Output {
    fn write(&mut self, buf: &[u8]) -> std::io::Result<usize> {
        let mut start = 0usize;
        let mut rem = buf.len();
        while rem > 0 {
            let len = (self.buf.len() - self.at).min(rem);
            self.buf[self.at..self.at + len].copy_from_slice(&buf[start..start + len]);
            self.at += len;
            if self.at == self.buf.len() {
                self.flush();
            }
            start += len;
            rem -= len;
        }
        if self.auto_flush {
            self.flush();
        }
        Ok(buf.len())
    }

    fn flush(&mut self) -> std::io::Result<()> {
        self.flush();
        Ok(())
    }
}

pub trait Writable {
    fn write(&self, output: &mut Output);
}

impl Writable for &str {
    fn write(&self, output: &mut Output) {
        output.write_all(self.as_bytes()).unwrap();
    }
}

impl Writable for String {
    fn write(&self, output: &mut Output) {
        output.write_all(self.as_bytes()).unwrap();
    }
}

impl Writable for char {
    fn write(&self, output: &mut Output) {
        output.put(*self as u8);
    }
}

impl<T: Writable> Writable for [T] {
    fn write(&self, output: &mut Output) {
        output.print_iter_ref(self.iter());
    }
}

impl<T: Writable> Writable for Vec<T> {
    fn write(&self, output: &mut Output) {
        self[..].write(output);
    }
}

macro_rules! write_to_string {
    ($t:ident) => {
        impl Writable for $t {
            fn write(&self, output: &mut Output) {
                self.to_string().write(output);
            }
        }
    };
}

write_to_string!(u8);
write_to_string!(u16);
write_to_string!(u32);
write_to_string!(u64);
write_to_string!(u128);
write_to_string!(usize);
write_to_string!(i8);
write_to_string!(i16);
write_to_string!(i32);
write_to_string!(i64);
write_to_string!(i128);
write_to_string!(isize);
write_to_string!(f32);
write_to_string!(f64);

impl<T: Writable, U: Writable> Writable for (T, U) {
    fn write(&self, output: &mut Output) {
        self.0.write(output);
        output.put(b' ');
        self.1.write(output);
    }
}

impl<T: Writable, U: Writable, V: Writable> Writable for (T, U, V) {
    fn write(&self, output: &mut Output) {
        self.0.write(output);
        output.put(b' ');
        self.1.write(output);
        output.put(b' ');
        self.2.write(output);
    }
}
}
}
pub mod math {
pub mod modulo_runtime {
use crate::algo_lib::collections::last_exn::LastExn;
use crate::algo_lib::io::output::Output;
use crate::algo_lib::io::output::Writable;
use crate::algo_lib::misc::num_traits::ConvSimple;
use crate::algo_lib::misc::num_traits::HasConstants;
use std::io::Write;

#[derive(Copy, Clone, Eq, PartialEq, Default, Ord, PartialOrd)]
pub struct ModRuntime {
    value: i32,
    m: i32,
}

impl ModRuntime {
    fn assert_reasonable_pair(a: &Self, b: &Self) {
        assert_ne!(a.m, 0);
        assert_ne!(a.m, 0);
        assert_eq!(a.m, b.m);
    }

    fn rev_rec(a: i32, m: i32) -> i32 {
        if a == 1 {
            return a;
        }
        ((1 - Self::rev_rec(m % a, a) as i64 * m as i64) / a as i64 + m as i64) as i32
    }

    #[allow(dead_code)]
    pub fn inv(self) -> Self {
        Self {
            value: Self::rev_rec(self.value, self.m),
            m: self.m,
        }
    }

    #[allow(dead_code)]
    #[inline]
    pub fn new(mut x: i32, m: i32) -> Self {
        if x < 0 {
            x += m;
            if x < 0 {
                x %= m;
                x += m;
            }
        } else if x >= m {
            x -= m;
            if x >= m {
                x %= m;
            }
        }
        assert!(0 <= x && x < m);
        Self { value: x, m }
    }

    pub fn pown(self, pw: usize) -> Self {
        if pw == 0 {
            Self::new(1, self.m)
        } else if pw == 1 {
            self
        } else {
            let half = self.pown(pw / 2);
            let res = half * half;
            if pw % 2 == 0 {
                res
            } else {
                res * self
            }
        }
    }

    // TODO: `pw` should be [T], which implements "integer"
    pub fn pow_i128(self, pw: i128) -> Self {
        if pw == 0 {
            Self::new(1, self.m)
        } else if pw == 1 {
            self
        } else {
            let half = self.pow_i128(pw / 2);
            let res = half * half;
            if pw % 2 == 0 {
                res
            } else {
                res * self
            }
        }
    }

    pub fn gen_powers(base: Self, n: usize) -> Vec<Self> {
        let mut res = Vec::with_capacity(n);
        res.push(Self::ONE);
        for _ in 1..n {
            res.push(*res.last_exn() * base);
        }
        res
    }

    pub fn value(&self) -> i32 {
        self.value
    }
}

impl std::fmt::Display for ModRuntime {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        write!(f, "{}", self.value)
    }
}

impl std::fmt::Debug for ModRuntime {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        const MAX: usize = 100;
        if self.value <= MAX as i32 {
            write!(f, "{}", self.value)
        } else if self.value >= self.m - MAX as i32 {
            write!(f, "-{}", self.m - self.value)
        } else {
            // TODO: not all ..MAX has inverse
            // for denum in 1..MAX {
            //     for num in 1..MAX {
            //         if Self::new(num as i32, self.m) / Self::new(denum as i32, self.m) == *self {
            //             return write!(f, "{}/{}", num, denum);
            //         }
            //     }
            // }
            write!(f, "(?? {} ??)", self.value)
        }
    }
}

impl std::ops::Add for ModRuntime {
    type Output = Self;

    fn add(self, rhs: Self) -> Self::Output {
        Self::assert_reasonable_pair(&self, &rhs);
        let res = self.value as i64 + rhs.value as i64;
        if res >= self.m as i64 {
            ModRuntime::new((res - self.m as i64) as i32, self.m)
        } else {
            ModRuntime::new(res as i32, self.m)
        }
    }
}

impl std::ops::AddAssign for ModRuntime {
    fn add_assign(&mut self, rhs: Self) {
        Self::assert_reasonable_pair(self, &rhs);
        let z = *self + rhs;
        self.value = z.value;
    }
}

impl std::ops::Sub for ModRuntime {
    type Output = Self;

    fn sub(self, rhs: Self) -> Self::Output {
        Self::assert_reasonable_pair(&self, &rhs);
        let res = self.value - rhs.value;
        if res < 0 {
            ModRuntime::new(res + self.m, self.m)
        } else {
            ModRuntime::new(res, self.m)
        }
    }
}

impl std::ops::SubAssign for ModRuntime {
    fn sub_assign(&mut self, rhs: Self) {
        Self::assert_reasonable_pair(self, &rhs);
        self.value -= rhs.value;
        if self.value < 0 {
            self.value += self.m;
        }
    }
}

impl std::ops::Mul for ModRuntime {
    type Output = Self;

    fn mul(self, rhs: Self) -> Self::Output {
        Self::assert_reasonable_pair(&self, &rhs);
        let res = (self.value as i64) * (rhs.value as i64) % (self.m as i64);
        ModRuntime::new(res as i32, self.m)
    }
}

impl std::ops::MulAssign for ModRuntime {
    fn mul_assign(&mut self, rhs: Self) {
        Self::assert_reasonable_pair(self, &rhs);
        self.value = ((self.value as i64) * (rhs.value as i64) % (self.m as i64)) as i32;
    }
}

impl std::ops::Div for ModRuntime {
    type Output = Self;

    #[allow(clippy::suspicious_arithmetic_impl)]
    fn div(self, rhs: Self) -> Self::Output {
        Self::assert_reasonable_pair(&self, &rhs);
        let rhs_inv = rhs.inv();
        self * rhs_inv
    }
}

impl std::ops::DivAssign for ModRuntime {
    #[allow(clippy::suspicious_op_assign_impl)]
    fn div_assign(&mut self, rhs: Self) {
        Self::assert_reasonable_pair(self, &rhs);
        *self *= rhs.inv();
    }
}

impl std::ops::Neg for ModRuntime {
    type Output = Self;

    fn neg(self) -> Self::Output {
        Self::assert_reasonable_pair(&self, &self);
        Self::new(self.m - self.value, self.m)
    }
}

impl Writable for ModRuntime {
    fn write(&self, output: &mut Output) {
        output.write_fmt(format_args!("{}", self.value)).unwrap();
    }
}

impl HasConstants<ModRuntime> for ModRuntime {
    // This doesn't make much sense, but hope we never use
    const MAX: ModRuntime = unreachable!();
    const MIN: ModRuntime = unreachable!();
    const ZERO: ModRuntime = unreachable!();
    const ONE: ModRuntime = ModRuntime { value: 0, m: 0 };
    const TWO: ModRuntime = unreachable!();
}

impl ConvSimple<ModRuntime> for ModRuntime {
    fn from_i32(_val: i32) -> ModRuntime {
        unreachable!()
    }

    fn to_i32(self) -> i32 {
        self.value
    }

    fn to_f64(self) -> f64 {
        self.value as f64
    }
}

pub struct RuntimeModBuilder {
    modulo: i32,
}

impl RuntimeModBuilder {
    pub fn new_builder(modulo: i32) -> Self {
        Self { modulo }
    }

    #[allow(clippy::new_ret_no_self)]
    pub fn new(&self, x: i32) -> ModRuntime {
        ModRuntime {
            value: x,
            m: self.modulo,
        }
    }
}
}
}
pub mod misc {
pub mod dbg_macro {
#[macro_export]
#[allow(unused_macros)]
macro_rules! dbg {
    ($first_val:expr, $($val:expr),+ $(,)?) => {
        eprint!("[{}:{}] {} = {:?}",
                    file!(), line!(), stringify!($first_val), &$first_val);
        ($(eprint!(", {} = {:?}", stringify!($val), &$val)),+,);
        eprintln!();
    };
    ($first_val:expr) => {
        eprintln!("[{}:{}] {} = {:?}",
                    file!(), line!(), stringify!($first_val), &$first_val)
    };
}
}
pub mod num_traits {
use std::cmp::Ordering;
use std::fmt::Debug;
use std::ops::Add;
use std::ops::AddAssign;
use std::ops::Div;
use std::ops::DivAssign;
use std::ops::Mul;
use std::ops::MulAssign;
use std::ops::Sub;
use std::ops::SubAssign;

pub trait HasConstants<T> {
    const MAX: T;
    const MIN: T;
    const ZERO: T;
    const ONE: T;
    const TWO: T;
}

pub trait ConvSimple<T> {
    fn from_i32(val: i32) -> T;
    fn to_i32(self) -> i32;
    fn to_f64(self) -> f64;
}

pub trait Signum {
    fn signum(&self) -> i32;
}

pub trait Number:
    Copy
    + Add<Output = Self>
    + AddAssign
    + Sub<Output = Self>
    + SubAssign
    + Mul<Output = Self>
    + MulAssign
    + Div<Output = Self>
    + DivAssign
    + PartialOrd
    + PartialEq
    + HasConstants<Self>
    + Default
    + Debug
    + Sized
    + ConvSimple<Self>
{
}

impl<
        T: Copy
            + Add<Output = Self>
            + AddAssign
            + Sub<Output = Self>
            + SubAssign
            + Mul<Output = Self>
            + MulAssign
            + Div<Output = Self>
            + DivAssign
            + PartialOrd
            + PartialEq
            + HasConstants<Self>
            + Default
            + Debug
            + Sized
            + ConvSimple<Self>,
    > Number for T
{
}

macro_rules! has_constants_impl {
    ($t: ident) => {
        impl HasConstants<$t> for $t {
            // TODO: remove `std` for new rust version..
            const MAX: $t = std::$t::MAX;
            const MIN: $t = std::$t::MIN;
            const ZERO: $t = 0;
            const ONE: $t = 1;
            const TWO: $t = 2;
        }

        impl ConvSimple<$t> for $t {
            fn from_i32(val: i32) -> $t {
                val as $t
            }

            fn to_i32(self) -> i32 {
                self as i32
            }

            fn to_f64(self) -> f64 {
                self as f64
            }
        }
    };
}

has_constants_impl!(i32);
has_constants_impl!(i64);
has_constants_impl!(i128);
has_constants_impl!(u32);
has_constants_impl!(u64);
has_constants_impl!(u128);
has_constants_impl!(usize);
has_constants_impl!(u8);

impl ConvSimple<Self> for f64 {
    fn from_i32(val: i32) -> Self {
        val as f64
    }

    fn to_i32(self) -> i32 {
        self as i32
    }

    fn to_f64(self) -> f64 {
        self
    }
}

impl HasConstants<Self> for f64 {
    const MAX: Self = Self::MAX;
    const MIN: Self = -Self::MAX;
    const ZERO: Self = 0.0;
    const ONE: Self = 1.0;
    const TWO: Self = 2.0;
}

impl<T: Number + Ord> Signum for T {
    fn signum(&self) -> i32 {
        match self.cmp(&T::ZERO) {
            Ordering::Greater => 1,
            Ordering::Less => -1,
            Ordering::Equal => 0,
        }
    }
}
}
}
}
fn main() {
    let input = algo_lib::io::input::Input::new_stdin();
    let mut output = algo_lib::io::output::Output::new_stdout();
    crate::solution::run(input, output);
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 2284kb

input:

5
1 1000000007 0 1 0
2 1000000007 0 1 1
2 7 5 2 3
3 31 15 6 24
20 1000000007 0 1 0

output:

1
12
1
21
879705565

result:

ok 5 number(s): "1 12 1 21 879705565"

Test #2:

score: 0
Accepted
time: 764ms
memory: 2688kb

input:

4400
3954 1000000007 0 1 0
1306 1000000007 0 1 0
3774 1000000007 0 1 0
3345 1000000007 0 1 0
891 1000000007 0 1 0
2462 1000000007 0 1 0
237 1000000007 0 1 0
26 1000000007 0 1 0
2510 1000000007 0 1 0
637 1000000007 0 1 0
3250 1000000007 0 1 0
3447 1000000007 0 1 0
1222 1000000007 0 1 0
133 1000000007...

output:

440618338
378292891
979368645
915766295
343598158
80867595
161627927
517387931
396936703
42785642
945720545
764273281
186237656
635777911
164064906
548455037
991964184
468137124
561243246
118562285
856945294
642467240
23673926
808943705
897417615
462422554
656411244
204288121
997894281
244685651
762...

result:

ok 4400 numbers

Test #3:

score: 0
Accepted
time: 809ms
memory: 86728kb

input:

1019
338 1863833207 1820742817 1507924477 1822273457
770 1386304741 1088481071 1216187083 170973217
597 1604266739 620750027 196415899 456280997
105 1008587891 184044403 24836083 926135599
357 1165127407 440925347 1103369747 912263123
82 1639766993 263045351 631010551 1412721139
928 1715915153 25383...

output:

1532578211
839037587
1047387343
827110887
825754860
1399761197
267796211
1563605211
1628148612
510782452
1009499206
977929696
466163317
246777775
1781337180
700999207
522771237
42312781
172374583
319038379
563256698
1400403161
22552986
1408276343
558752169
1050819260
174447415
844160548
1382940913
1...

result:

ok 1019 numbers

Test #4:

score: 0
Accepted
time: 801ms
memory: 10648kb

input:

217
31752 1623636743 381890923 885513569 842557939
44560 1671300349 1133398261 1076377361 138151151
98395 1887613031 1552853849 1167776639 1748368931
38388 1221893927 524645339 598717199 864504559
46484 1161165839 833729009 348202331 407607601
14134 1500136753 247946861 1029519499 420912461
42361 12...

output:

921943129
1651287678
1204818336
685557670
348324702
1348834532
684106754
1802861733
294146103
1181847835
393402724
771264676
1357541910
336262290
1519052686
965265375
164416232
536332209
664177339
279762508
172270575
296113856
676553568
56580590
1662307723
551032870
849878353
899756098
1043540760
65...

result:

ok 217 numbers

Test #5:

score: 0
Accepted
time: 823ms
memory: 10772kb

input:

209
29771 1072350767 215063557 929759989 884416571
55201 1330151437 375869047 1089916759 1006803043
44446 1255569503 974485139 1100573447 468049237
38112 1088575729 690554509 139043089 318478729
59665 1197676111 958924997 1062562733 504417349
26297 1267535141 800679281 972314209 417253079
19848 1470...

output:

1019773842
530587777
960231793
799694163
777561611
5502176
357632543
758954057
966358573
1023410809
949841520
1495179331
1580320049
173875471
2220116
469298866
1337750009
369625733
747522220
143937247
1286370836
135996013
210044979
1583248565
657653951
1035620126
160616212
193166047
147168296
194451...

result:

ok 209 numbers

Test #6:

score: 0
Accepted
time: 807ms
memory: 10884kb

input:

191
4581 1215490597 542057431 695641117 341312327
76198 1830024701 1063458349 588883499 1260572737
76694 1445111947 1069466003 941483509 268919069
92431 1384691513 15731591 390776461 943271249
63234 1097808793 204272807 857954509 763222181
26427 1746295877 743699191 1671886939 1655403307
91012 19997...

output:

660812054
1707568418
155249600
645552623
671226426
50129037
971925203
1638809868
463571080
143058581
403506184
767222482
666935871
1092771100
416048275
1536775747
475955650
73199758
578511368
51576569
1380151783
515363742
1021989523
892069331
1088408017
1337534689
715624643
1241212077
730954505
1286...

result:

ok 191 numbers

Extra Test:

score: 0
Extra Test Passed