結果
問題 | No.2568 列辞書順列列 |
ユーザー |
![]() |
提出日時 | 2023-11-27 17:14:29 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 209 ms / 3,000 ms |
コード長 | 2,788 bytes |
コンパイル時間 | 13,519 ms |
コンパイル使用メモリ | 378,984 KB |
実行使用メモリ | 9,856 KB |
最終ジャッジ日時 | 2024-09-26 12:30:40 |
合計ジャッジ時間 | 22,809 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 25 |
ソースコード
use std::vec;macro_rules! input {($($r:tt)*) => {let stdin = std::io::stdin();let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));let mut next = move || -> String{bytes.by_ref().map(|r|r.unwrap() as char).skip_while(|c|c.is_whitespace()).take_while(|c|!c.is_whitespace()).collect()};input_inner!{next, $($r)*}};}macro_rules! input_inner {($next:expr) => {};($next:expr,) => {};($next:expr, $var:ident : $t:tt $($r:tt)*) => {let $var = read_value!($next, $t);input_inner!{$next $($r)*}};}macro_rules! read_value {($next:expr, ( $($t:tt),* )) => { ($(read_value!($next, $t)),*) };($next:expr, [ $t:tt ; $len:expr ]) => {(0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()};($next:expr, $t:ty) => ($next().parse::<$t>().expect("Parse error"));}#[derive(Debug, Clone, Copy)]struct ModInt {value: usize,}impl ModInt {fn modulo() -> usize {998244353}fn new(value: usize) -> Self {Self {value: value % Self::modulo(),}}fn pow(self, n: usize) -> Self {let mut res = Self::new(1);let mut x = self;let mut n = n;while n > 0 {if n & 1 == 1 {res = res * x;}x = x * x;n >>= 1;}res}}impl std::ops::Add for ModInt {type Output = Self;fn add(self, rhs: Self) -> Self {Self::new(self.value + rhs.value)}}impl std::ops::Sub for ModInt {type Output = Self;fn sub(self, rhs: Self) -> Self {Self::new(self.value + Self::modulo() - rhs.value)}}impl std::ops::Mul for ModInt {type Output = Self;fn mul(self, rhs: Self) -> Self {Self::new(self.value * rhs.value)}}impl std::ops::Div for ModInt {type Output = Self;fn div(self, rhs: Self) -> Self {self * rhs.pow(Self::modulo() - 2)}}fn main() {input! {n: usize,m: usize,q: usize,a: [usize; n],query: [(usize, usize); q],}let m = ModInt::new(m);let m_pow = (0..n).map(|i| m.pow(i)).collect::<Vec<_>>();let b = (0..n).map(|i| ModInt::new(a[i] - 1) * m_pow[n - i - 1]).collect::<Vec<_>>();let cs = {let mut cs = vec![ModInt::new(0); 1];for &b in &b {cs.push(cs[cs.len() - 1] + b);}cs};for (l, r) in query {let l = l - 1;let sum = cs[r] - cs[l];let ans = sum / m_pow[n - r] + ModInt::new(1);println!("{}", ans.value);}}