結果
| 問題 | No.2791 Beginner Contest |
| ユーザー |
 naut3
|
| 提出日時 | 2024-06-22 00:09:05 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 5 ms / 2,000 ms |
| コード長 | 6,966 bytes |
| コンパイル時間 | 13,706 ms |
| コンパイル使用メモリ | 401,668 KB |
| 実行使用メモリ | 6,944 KB |
| 最終ジャッジ日時 | 2024-06-22 00:09:22 |
| 合計ジャッジ時間 | 15,426 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 17 |
ソースコード
#![allow(non_snake_case, unused_imports)]use proconio::{fastout, input, marker::*};type MInt = ModInt<998244353>;#[fastout]fn main() {input! {N: usize, K: usize,}let mut dp = BinaryIndexedTree::new(N + 1);dp.add(0, MInt::from_raw(1));for i in K..=N {let s = dp.sum(0..=i - K);dp.add(i, s);}let ans = dp.sum(0..=N);println!("{}", ans);}pub struct BinaryIndexedTree<T> {tree: Vec<T>,}impl<T: Default + Clone + Copy + std::ops::AddAssign + std::ops::Sub<Output = T>>BinaryIndexedTree<T>{/// self = [0; size]pub fn new(size: usize) -> Self {return Self {tree: vec![T::default(); size + 1],};}/// self[i] <- self[i] + wpub fn add(&mut self, i: usize, w: T) {self._add(i + 1, w);}/// return Σ_{j ∈ [0, i]} self[j]pub fn prefix_sum(&self, i: usize) -> T {self._sum(i + 1)}/// return Σ_{j ∈ range} self[j]pub fn sum<R: std::ops::RangeBounds<usize>>(&self, range: R) -> T {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() - 2,};if left == 0 {return self.prefix_sum(right);} else {return self.prefix_sum(right) - self.prefix_sum(left - 1);}}fn _add(&mut self, mut i: usize, w: T) {while i < self.tree.len() {self.tree[i] += w;i += i & i.wrapping_neg();}}fn _sum(&self, mut i: usize) -> T {let mut ret = T::default();while i > 0 {ret += self.tree[i];i -= i & i.wrapping_neg();}return ret;}}#[derive(Clone, Copy, PartialEq, Eq, Debug, Default)]pub struct ModInt<const P: u32>(u32);impl<const P: u32> ModInt<P> {pub fn value(&self) -> u32 {return self.0;}pub fn new() -> Self {Self(0)}pub fn from_raw(value: u32) -> Self {Self(value)}pub fn inv(&self) -> Self {self.pow(P as u64 - 2)}pub fn pow(&self, mut x: u64) -> Self {let mut a = self.clone();let mut r = Self::from_raw(1);while x > 0 {if x & 1 == 1 {r *= a;}a *= a;x >>= 1;}r}}macro_rules! impl_to_integer_types {($($t: ty), *) => {$(impl<const P: u32> From<$t> for ModInt<P> {fn from(value: $t) -> Self {let v = ((value % (P as $t)) + P as $t) as u32;Self(if v >= P { v - P } else { v })}}impl<const P: u32> std::ops::Add<$t> for ModInt<P> {type Output = Self;fn add(self, rhs: $t) -> Self::Output {self + ModInt::<P>::from(rhs)}}impl<const P: u32> std::ops::AddAssign<$t> for ModInt<P> {fn add_assign(&mut self, rhs: $t) {self.0 += ModInt::<P>::from(rhs).0;if self.0 >= P {self.0 -= P;}}}impl<const P: u32> std::ops::Sub<$t> for ModInt<P> {type Output = Self;fn sub(self, rhs: $t) -> Self::Output {self - ModInt::<P>::from(rhs)}}impl<const P: u32> std::ops::SubAssign<$t> for ModInt<P> {fn sub_assign(&mut self, rhs: $t) {let m = ModInt::<P>::from(rhs);if self.0 >= m.0 {self.0 -= m.0;} else {self.0 += P - m.0;}}}impl<const P: u32> std::ops::Mul<$t> for ModInt<P> {type Output = Self;fn mul(self, rhs: $t) -> Self::Output {self * ModInt::<P>::from(rhs)}}impl<const P: u32> std::ops::MulAssign<$t> for ModInt<P> {fn mul_assign(&mut self, rhs: $t) {let r = self.0 as u64;self.0 = ((r * ModInt::<P>::from(rhs).0 as u64) % P as u64) as u32;}}impl<const P: u32> std::ops::Div<$t> for ModInt<P> {type Output = Self;fn div(self, rhs: $t) -> Self::Output {self / ModInt::<P>::from(rhs)}}impl<const P: u32> std::ops::DivAssign<$t> for ModInt<P> {fn div_assign(&mut self, rhs: $t) {*self *= ModInt::<P>::from(rhs).inv();}})*};}impl_to_integer_types!(usize, isize, u64, i64, u32, i32);impl<const P: u32> std::ops::Add for ModInt<P> {type Output = Self;fn add(self, rhs: Self) -> Self::Output {let r = self.0 + rhs.0;Self(if r >= P { r - P } else { r })}}impl<const P: u32> std::ops::AddAssign for ModInt<P> {fn add_assign(&mut self, rhs: Self) {self.0 += rhs.0;if self.0 >= P {self.0 -= P;}}}impl<const P: u32> std::ops::Sub for ModInt<P> {type Output = Self;fn sub(self, rhs: Self) -> Self::Output {Self(if self.0 >= rhs.0 {self.0 - rhs.0} else {P + self.0 - rhs.0})}}impl<const P: u32> std::ops::SubAssign for ModInt<P> {fn sub_assign(&mut self, rhs: Self) {if self.0 >= rhs.0 {self.0 -= rhs.0;} else {self.0 += P - rhs.0;}}}impl<const P: u32> std::ops::Mul for ModInt<P> {type Output = Self;fn mul(self, rhs: Self) -> Self::Output {Self(((self.0 as u64 * rhs.0 as u64) % P as u64) as u32)}}impl<const P: u32> std::ops::MulAssign for ModInt<P> {fn mul_assign(&mut self, rhs: Self) {let r = self.0 as u64;self.0 = ((r * rhs.0 as u64) % P as u64) as u32;}}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 *= rhs.inv();}}impl<const P: u32> std::fmt::Display for ModInt<P> {fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {write!(f, "{}", self.0)}}