提出 #19251679

---

ソースコード 拡げる

use std::collections::BTreeSet;

use mod_int::{set_mod_int, ModInt};

const MOD: i64 = 1e9 as i64 + 7;
fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());
    set_mod_int(MOD);

    let n: usize = sc.read();
    let m: usize = sc.read();
    let f: Vec<i64> = sc.vec(n);
    let mut seg_set = BTreeSet::new();

    let mut seg = vec![0; n];
    let mut right = 0;
    for left in 0..n {
        while right < n && !seg_set.contains(&f[right]) {
            seg_set.insert(f[right]);
            right += 1;
        }
        seg[left] = right;
        seg_set.remove(&f[left]);
    }

    let mut sum = vec![m_int(0); n + 1];
    let mut cur = m_int(0);

    sum[0] += 1;
    sum[seg[0]] -= 1;

    for pos in 0..n {
        cur += sum[pos];
        let next_start = pos + 1;
        let next_end = if next_start < n { seg[next_start] } else { n };
        sum[next_start] += cur;
        sum[next_end] -= cur;
        // eprintln!("{} {}", next_start, cur.value());
    }

    println!("{}", cur.value());
}

fn m_int(v: i64) -> ModInt {
    ModInt::new(v)
}
pub struct Combination {
    fact: Vec<usize>,
    inv_fact: Vec<usize>,
    modulo: usize,
}

impl Combination {
    pub fn new(max: usize, modulo: usize) -> Self {
        let mut inv = vec![0; max + 1];
        let mut fact = vec![0; max + 1];
        let mut inv_fact = vec![0; max + 1];
        inv[1] = 1;
        for i in 2..(max + 1) {
            inv[i] = inv[modulo % i] * (modulo - modulo / i) % modulo;
        }
        fact[0] = 1;
        inv_fact[0] = 1;
        for i in 0..max {
            fact[i + 1] = fact[i] * (i + 1) % modulo;
        }
        for i in 0..max {
            inv_fact[i + 1] = inv_fact[i] * inv[i + 1] % modulo;
        }
        Self {
            fact,
            inv_fact,
            modulo,
        }
    }

    pub fn get(&self, x: usize, y: usize) -> usize {
        assert!(x >= y);
        self.fact[x] * self.inv_fact[y] % self.modulo * self.inv_fact[x - y] % self.modulo
    }

    pub fn h(&self, n: usize, r: usize) -> usize {
        self.get(n + r - 1, r)
    }
}
pub mod mod_int {
    use std::cell::RefCell;
    use std::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Sub, SubAssign};

    type InternalNum = i64;
    thread_local!(
        static MOD: RefCell<InternalNum> = RefCell::new(0);
    );

    pub fn set_mod_int<T>(v: T)
    where
        InternalNum: From<T>,
    {
        MOD.with(|x| x.replace(InternalNum::from(v)));
    }
    fn modulo() -> InternalNum {
        MOD.with(|x| *x.borrow())
    }

    pub struct ModInt(InternalNum);
    impl Clone for ModInt {
        fn clone(&self) -> Self {
            Self(self.0)
        }
    }
    impl Copy for ModInt {}

    impl ModInt {
        pub fn new<T>(v: T) -> Self
        where
            InternalNum: From<T>,
        {
            let mut v = InternalNum::from(v);
            let m = modulo();
            if v >= m {
                v %= m;
            }
            Self(v)
        }

        pub fn internal_pow(&self, mut e: InternalNum) -> Self {
            let mut result = 1;
            let mut cur = self.0;
            let modulo = modulo();
            while e > 0 {
                if e & 1 == 1 {
                    result *= cur;
                    result %= modulo;
                }
                e >>= 1;
                cur = (cur * cur) % modulo;
            }
            Self(result)
        }

        pub fn pow<T>(&self, e: T) -> Self
        where
            InternalNum: From<T>,
        {
            self.internal_pow(InternalNum::from(e))
        }

        pub fn value(&self) -> InternalNum {
            self.0
        }
    }
    impl From<ModInt> for InternalNum {
        fn from(m: ModInt) -> Self {
            m.value()
        }
    }

    impl<T> AddAssign<T> for ModInt
    where
        InternalNum: From<T>,
    {
        fn add_assign(&mut self, rhs: T) {
            let mut rhs = InternalNum::from(rhs);
            let m = modulo();
            if rhs >= m {
                rhs %= m;
            }

            self.0 += rhs;
            if self.0 >= m {
                self.0 -= m;
            }
        }
    }

    impl<T> Add<T> for ModInt
    where
        InternalNum: From<T>,
    {
        type Output = ModInt;
        fn add(self, rhs: T) -> Self::Output {
            let mut res = self;
            res += rhs;
            res
        }
    }
    impl<T> SubAssign<T> for ModInt
    where
        InternalNum: From<T>,
    {
        fn sub_assign(&mut self, rhs: T) {
            let mut rhs = InternalNum::from(rhs);
            let m = modulo();
            if rhs >= m {
                rhs %= m;
            }
            if rhs > 0 {
                self.0 += m - rhs;
            }
            if self.0 >= m {
                self.0 -= m;
            }
        }
    }
    impl<T> Sub<T> for ModInt
    where
        InternalNum: From<T>,
    {
        type Output = Self;
        fn sub(self, rhs: T) -> Self::Output {
            let mut res = self;
            res -= rhs;
            res
        }
    }
    impl<T> MulAssign<T> for ModInt
    where
        InternalNum: From<T>,
    {
        fn mul_assign(&mut self, rhs: T) {
            let mut rhs = InternalNum::from(rhs);
            let m = modulo();
            if rhs >= m {
                rhs %= m;
            }
            self.0 *= rhs;
            self.0 %= m;
        }
    }
    impl<T> Mul<T> for ModInt
    where
        InternalNum: From<T>,
    {
        type Output = Self;
        fn mul(self, rhs: T) -> Self::Output {
            let mut res = self;
            res *= rhs;
            res
        }
    }

    impl<T> DivAssign<T> for ModInt
    where
        InternalNum: From<T>,
    {
        fn div_assign(&mut self, rhs: T) {
            let mut rhs = InternalNum::from(rhs);
            let m = modulo();
            if rhs >= m {
                rhs %= m;
            }
            let inv = Self(rhs).internal_pow(m - 2);
            self.0 *= inv.value();
            self.0 %= m;
        }
    }

    impl<T> Div<T> for ModInt
    where
        InternalNum: From<T>,
    {
        type Output = Self;
        fn div(self, rhs: T) -> Self::Output {
            let mut res = self;
            res /= rhs;
            res
        }
    }
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> Self {
        Self(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write_all(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

提出情報

コンパイルエラー

warning: unused variable: `m`
  --> src/main.rs:12:9
   |
12 |     let m: usize = sc.read();
   |         ^ help: consider prefixing with an underscore: `_m`
   |
   = note: `#[warn(unused_variables)]` on by default

ジャッジ結果