結果

問題 No.2561 みんな大好きmod 998
コンテスト
ユーザー ぱるま
提出日時 2023-12-02 15:21:20
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 103 ms / 4,000 ms
コード長 7,069 bytes
コンパイル時間 13,180 ms
コンパイル使用メモリ 379,376 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-26 18:31:51
合計ジャッジ時間 15,947 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 44
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: method `solve_old` is never used
  --> src/main.rs:15:8
   |
9  | impl Problem {
   | ------------ method in this implementation
...
15 |     fn solve_old(&self) -> Answer {
   |        ^^^^^^^^^
   |
   = note: `#[warn(dead_code)]` on by default

warning: function `combinations` is never used
  --> src/main.rs:56:4
   |
56 | fn combinations(n: usize, k: usize) -> Vec<Vec<i64>> {
   |    ^^^^^^^^^^^^

ソースコード

diff # 

use std::io::stdin;

struct Problem {
    n: usize,
    k: usize,
    xs: Vec<i64>,
}

impl Problem {
    fn read<R: IProconReader>(mut r: R) -> Problem {
        let (n, k) = r.read_usize_2();
        let xs = r.read_vec_any();
        Problem { n, k, xs }
    }
    fn solve_old(&self) -> Answer {
        let comb = combinations(self.n, self.k);
        let ans = comb
            .iter()
            .filter(|bs| {
                let sum = self.xs.iter().zip(bs.iter()).map(|(x, b)| x * b).sum::<i64>();
                let sum_998244353 = sum % 998244353;
                let sum_998 = sum % 998;
                sum_998244353 <= sum_998
            })
            .count() as i64;
        let ans = ans % 998;
        Answer { ans }
    }

    fn solve(&self) -> Answer {
        let n = self.n;
        let k = self.k;
        let mut seq01 = std::iter::repeat(0)
            .take(n - k)
            .chain(std::iter::repeat(1).take(k))
            .collect::<Vec<_>>();

        let mut cnt = 0;

        while {
            let sum = self.xs.iter().zip(seq01.iter()).map(|(x, b)| x * b).sum::<i64>();
            let sum_998244353 = sum % 998244353;
            let sum_998 = sum % 998;
            if sum_998244353 <= sum_998{
                cnt += 1;
            }

            next_permutation(&mut seq01)
        } {}

        let ans = cnt % 998;
        Answer { ans }
    }
}

fn combinations(n: usize, k: usize) -> Vec<Vec<i64>> {
    let mut ret = Vec::new();
    // 0 を n-k 個, 1をk個並べる
    let mut seq01 =
        std::iter::repeat(0).take(n - k).chain(std::iter::repeat(1).take(k)).collect::<Vec<_>>();

    while {
        ret.push(seq01.clone());
        next_permutation(&mut seq01)
    } {}
    ret
}

// https://ngtkana.hatenablog.com/entry/2021/11/08/000209
pub fn next_permutation<T: Ord>(a: &mut [T]) -> bool {
    if a.is_empty() {
        return false;
    }
    let Some(i) = (0..a.len() - 1).rfind(|&i| a[i] < a[i + 1]) else { return false };
    let j = a.iter().rposition(|x| x > &a[i]).unwrap();
    a.swap(i, j);
    a[i + 1..].reverse();
    true
}

#[derive(Clone, Debug, PartialEq, Eq)]
struct Answer {
    ans: i64,
}

impl Answer {
    fn print(&self) {
        println!("{}", self.ans);
    }
}

fn main() {
    Problem::read(ProconReader::new(stdin().lock())).solve().print();
}

#[cfg(test)]
mod tests {
    use super::*;

    #[allow(dead_code)]
    fn check(input: &str, expected: Answer) {
        let actual = Problem::read(ProconReader::new(input.as_bytes())).solve();
        assert_eq!(expected, actual);
    }

    #[test]
    fn test_problem() {
        let _input = "
3
4
        "
        .trim();
        // check(_input, Answer { ans: 7 });
    }
}

// ====== snippet ======

#[allow(unused_imports)]
use myio::*;
pub mod myio {
    use std::io::BufRead;

    pub trait IProconReader {
        fn read_line(&mut self) -> String;

        fn read_bytes(&mut self) -> Vec<u8> {
            self.read_line().as_bytes().to_vec()
        }

        fn read_any_1<T>(&mut self) -> T
        where
            T: std::str::FromStr,
            T::Err: std::fmt::Debug,
        {
            let buf = self.read_line();
            buf.parse::<T>().unwrap()
        }

        fn read_any_2<T0, T1>(&mut self) -> (T0, T1)
        where
            T0: std::str::FromStr,
            T0::Err: std::fmt::Debug,
            T1: std::str::FromStr,
            T1::Err: std::fmt::Debug,
        {
            let buf = self.read_line();
            let splitted = buf.trim().split(' ').collect::<Vec<_>>();
            let a0 = splitted[0].parse::<T0>().unwrap();
            let a1 = splitted[1].parse::<T1>().unwrap();
            (a0, a1)
        }

        fn read_any_3<T0, T1, T2>(&mut self) -> (T0, T1, T2)
        where
            T0: std::str::FromStr,
            T0::Err: std::fmt::Debug,
            T1: std::str::FromStr,
            T1::Err: std::fmt::Debug,
            T2: std::str::FromStr,
            T2::Err: std::fmt::Debug,
        {
            let buf = self.read_line();
            let splitted = buf.trim().split(' ').collect::<Vec<_>>();
            let a0 = splitted[0].parse::<T0>().unwrap();
            let a1 = splitted[1].parse::<T1>().unwrap();
            let a2 = splitted[2].parse::<T2>().unwrap();
            (a0, a1, a2)
        }

        fn read_any_4<T0, T1, T2, T3>(&mut self) -> (T0, T1, T2, T3)
        where
            T0: std::str::FromStr,
            T0::Err: std::fmt::Debug,
            T1: std::str::FromStr,
            T1::Err: std::fmt::Debug,
            T2: std::str::FromStr,
            T2::Err: std::fmt::Debug,
            T3: std::str::FromStr,
            T3::Err: std::fmt::Debug,
        {
            let buf = self.read_line();
            let splitted = buf.trim().split(' ').collect::<Vec<_>>();
            let a0 = splitted[0].parse::<T0>().unwrap();
            let a1 = splitted[1].parse::<T1>().unwrap();
            let a2 = splitted[2].parse::<T2>().unwrap();
            let a3 = splitted[3].parse::<T3>().unwrap();
            (a0, a1, a2, a3)
        }
        fn read_vec_any<T>(&mut self) -> Vec<T>
        where
            T: std::str::FromStr,
            T::Err: std::fmt::Debug,
        {
            let buf = self.read_line();
            buf.trim().split(' ').map(|s| s.parse::<T>().unwrap()).collect::<Vec<T>>()
        }

        fn read_vec_i64(&mut self) -> Vec<i64> {
            self.read_vec_any::<i64>()
        }

        fn read_vec_usize(&mut self) -> Vec<usize> {
            self.read_vec_any::<usize>()
        }

        fn read_vec_str(&mut self) -> Vec<String> {
            self.read_vec_any::<String>()
        }

        fn read_i64_1(&mut self) -> i64 {
            self.read_any_1::<i64>()
        }

        fn read_i64_2(&mut self) -> (i64, i64) {
            self.read_any_2::<i64, i64>()
        }

        fn read_i64_3(&mut self) -> (i64, i64, i64) {
            self.read_any_3::<i64, i64, i64>()
        }

        fn read_i64_4(&mut self) -> (i64, i64, i64, i64) {
            self.read_any_4::<i64, i64, i64, i64>()
        }

        fn read_usize_1(&mut self) -> usize {
            self.read_any_1::<usize>()
        }

        fn read_usize_2(&mut self) -> (usize, usize) {
            self.read_any_2::<usize, usize>()
        }

        fn read_usize_3(&mut self) -> (usize, usize, usize) {
            self.read_any_3::<usize, usize, usize>()
        }

        fn read_usize_4(&mut self) -> (usize, usize, usize, usize) {
            self.read_any_4::<usize, usize, usize, usize>()
        }
    }

    pub struct ProconReader<R: BufRead> {
        buf_read: R,
    }

    impl<R: BufRead> ProconReader<R> {
        pub fn new(buf_read: R) -> ProconReader<R> {
            ProconReader { buf_read }
        }
    }

    impl<R: BufRead> IProconReader for ProconReader<R> {
        fn read_line(&mut self) -> String {
            let mut buffer = String::new();
            self.buf_read.read_line(&mut buffer).unwrap();
            buffer.trim().to_string()
        }
    }
}
0