結果
問題 | No.2625 Bouns Ai |
ユーザー |
![]() |
提出日時 | 2024-02-09 23:18:20 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 652 ms / 2,000 ms |
コード長 | 7,710 bytes |
コンパイル時間 | 11,309 ms |
コンパイル使用メモリ | 402,208 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-09-28 16:30:35 |
合計ジャッジ時間 | 26,140 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#![allow(non_snake_case, unused_imports, unused_must_use)]use std::io::{self, prelude::*};use std::str;fn main() {let (stdin, stdout) = (io::stdin(), io::stdout());let mut scan = Scanner::new(stdin.lock());let mut out = io::BufWriter::new(stdout.lock());macro_rules! input {($T: ty) => {scan.token::<$T>()};($T: ty, $N: expr) => {(0..$N).map(|_| scan.token::<$T>()).collect::<Vec<_>>()};}let N = input!(usize);let A = input!(usize, N);let mut dp = BinaryIndexedTree::new(100_001);for i in 0..=100_000 {if A[0] <= i {dp.add(i, ModInt::<998244353>::from_raw(1));}}for i in 1..N {let mut nxtdp = BinaryIndexedTree::new(100_001);for j in 0..=100_000 {let mut c = j as isize + A[i - 1] as isize - A[i] as isize;if c > 100_000 {c = 100_000;} else if c < 0 {continue;}let c = c as usize;nxtdp.add(j, dp.sum(0..=std::cmp::min(c, j)));}dp = nxtdp;}let ans = dp.sum(0..=100_000);writeln!(out, "{}", ans);}pub struct BinaryIndexedTree {tree: Vec<ModInt<998244353>>,}impl BinaryIndexedTree {pub fn new(size: usize) -> Self {return Self {tree: vec![ModInt::<998244353>::new(); size + 1],};}fn _inner_add(&mut self, mut i: usize, w: ModInt<998244353>) {while i < self.tree.len() {self.tree[i] += w;i += i & i.wrapping_neg();}}fn _inner_sum(&self, mut i: usize) -> ModInt<998244353> {let mut ret = ModInt::<998244353>::new();while i > 0 {ret += self.tree[i];i -= i & i.wrapping_neg();}return ret;}/// self.tree[i] += wpub fn add(&mut self, i: usize, w: ModInt<998244353>) {self._inner_add(i + 1, w);}/// return Σ_{j in [0, i]} self.tree[j]pub fn prefix_sum(&self, i: usize) -> ModInt<998244353> {self._inner_sum(i + 1)}/// return Σ_{j in range} self.tree[j]pub fn sum<R: std::ops::RangeBounds<usize>>(&self, range: R) -> ModInt<998244353> {let left = match range.start_bound() {std::ops::Bound::Included(&l) => l,std::ops::Bound::Excluded(&l) => l + 1,std::ops::Bound::Unbounded => 0,};let right = match range.end_bound() {std::ops::Bound::Included(&r) => r,std::ops::Bound::Excluded(&r) => r - 1,std::ops::Bound::Unbounded => self.tree.len() - 1,};if left == 0 {return self.prefix_sum(right);} else {return self.prefix_sum(right) - self.prefix_sum(left - 1);}}}#[derive(Clone, Copy, Eq, PartialEq, Debug)]pub struct ModInt<const P: u32> {value: u32,}impl<const P: u32> ModInt<P> {pub fn value(&self) -> u32 {assert!(self.value < P);return self.value;}pub fn new() -> Self {return Self { value: 0 };}pub fn from_raw(x: u32) -> Self {return Self { value: x };}pub fn from_usize(x: usize) -> Self {return Self {value: (x % P as usize) as u32,};}pub fn from_isize(x: isize) -> Self {let mut value = x % P as isize;if value < 0 {value += P as isize;}return Self {value: value as u32,};}pub fn inv(&self) -> Self {pub fn ext_gcd(a: isize, b: isize) -> (isize, isize) {let mut a_k = a;let mut b_k = b;let mut q_k = a_k / b_k;let mut r_k = a_k % b_k;let mut x_k = 0;let mut y_k = 1;let mut z_k = 1;let mut w_k = -q_k;a_k = b_k;b_k = r_k;while r_k != 0 {q_k = a_k / b_k;r_k = a_k % b_k;a_k = b_k;b_k = r_k;let nx = z_k;let ny = w_k;let nz = x_k - q_k * z_k;let nw = y_k - q_k * w_k;x_k = nx;y_k = ny;z_k = nz;w_k = nw;}(x_k, y_k)}let val = self.value() as isize;let ret = ext_gcd(val, P as isize).0;return Self::from_isize(ret);}pub fn pow(&self, mut x: u64) -> Self {let mut ret = ModInt::from_raw(1);let mut a = self.clone();while x > 0 {if (x & 1) == 1 {ret = ret * a;}a *= a;x >>= 1;}return ret;}}impl<const P: u32> std::ops::Add for ModInt<P> {type Output = Self;fn add(self, rhs: Self) -> Self::Output {let mut ret = self.value() + rhs.value();if ret >= P {ret -= P;}return Self::from_raw(ret);}}impl<const P: u32> std::ops::AddAssign for ModInt<P> {fn add_assign(&mut self, rhs: Self) {self.value = (self.clone() + rhs).value();}}impl<const P: u32> std::ops::Sub for ModInt<P> {type Output = Self;fn sub(self, rhs: Self) -> Self::Output {if self.value() >= rhs.value() {return Self::from_raw(self.value() - rhs.value());} else {return Self::from_raw(P + self.value() - rhs.value());}}}impl<const P: u32> std::ops::SubAssign for ModInt<P> {fn sub_assign(&mut self, rhs: Self) {self.value = (self.clone() - rhs).value();}}impl<const P: u32> std::ops::Mul for ModInt<P> {type Output = Self;fn mul(self, rhs: Self) -> Self::Output {let ret = self.value() as usize * rhs.value() as usize;return Self::from_usize(ret);}}impl<const P: u32> std::ops::MulAssign for ModInt<P> {fn mul_assign(&mut self, rhs: Self) {self.value = (self.clone() * rhs).value();}}impl<const P: u32> std::ops::Div for ModInt<P> {type Output = Self;fn div(self, rhs: Self) -> Self::Output {self * rhs.inv()}}impl<const P: u32> std::ops::DivAssign for ModInt<P> {fn div_assign(&mut self, rhs: Self) {self.value = (self.clone() / rhs).value();}}impl<const P: u32> std::ops::Neg for ModInt<P> {type Output = Self;fn neg(self) -> Self::Output {let value = self.value();return Self { value: P - value };}}impl<const P: u32> std::fmt::Display for ModInt<P> {fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {write!(f, "{}", self.value)}}struct Scanner<R> {reader: R,buf_str: Vec<u8>,buf_iter: str::SplitWhitespace<'static>,}impl<R: BufRead> Scanner<R> {fn new(reader: R) -> Self {Self {reader,buf_str: vec![],buf_iter: "".split_whitespace(),}}fn token<T: str::FromStr>(&mut self) -> T {loop {if let Some(token) = self.buf_iter.next() {return token.parse().ok().expect("Failed parse");}self.buf_str.clear();self.reader.read_until(b'\n', &mut self.buf_str).expect("Failed read");self.buf_iter = unsafe {let slice = str::from_utf8_unchecked(&self.buf_str);std::mem::transmute(slice.split_whitespace())}}}}