結果

問題 No.1621 Sequence Inversions
コンテスト
ユーザー Rheo Tommy
提出日時 2021-07-23 00:05:05
言語 Rust
(1.83.0 + proconio)
結果
TLE  
実行時間 -
コード長 11,016 bytes
コンパイル時間 13,690 ms
コンパイル使用メモリ 403,572 KB
実行使用メモリ 13,888 KB
最終ジャッジ日時 2024-07-17 21:23:36
合計ジャッジ時間 17,576 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(unused_macros)]
#![allow(dead_code)]
#![allow(unused_imports)]

// # ファイル構成
// - use 宣言
// - lib モジュール
// - main 関数
// - basic モジュール
//
// 常に使うテンプレートライブラリは basic モジュール内にあります。
// 問題に応じて使うライブラリ lib モジュール内にコピペしています。
// ライブラリのコードはこちら → https://github.com/RheoTommy/at_coder
// Twitter はこちら → https://twitter.com/RheoTommy

use std::collections::*;
use std::io::{stdout, BufWriter, Write};

use crate::basic::*;
use crate::lib::*;

pub mod lib {
    pub fn rle<T: Eq + Clone>(s: &[T]) -> Vec<(T, usize)> {
        let mut res: Vec<(T, usize)> = vec![];
        for si in s {
            if res.is_empty() || &(res[res.len() - 1].0) != si {
                res.push((si.clone(), 1));
            } else {
                let l = res.len();
                let (_, k) = &mut res[l - 1];
                *k += 1;
            }
        }
        res
    }

    pub type ModInt = StaticModInt;

    pub const MOD: i32 = MOD998244353;
    pub const MOD1000000007: i32 = 1000000007;
    pub const MOD998244353: i32 = 998244353;

    #[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd)]
    pub struct StaticModInt(i32);

    impl std::fmt::Display for StaticModInt {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            write!(f, "{}", self.0)
        }
    }

    impl std::fmt::Debug for StaticModInt {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            write!(f, "{}", self)
        }
    }

    impl StaticModInt {
        pub fn new<T: Into<StaticModInt>>(n: T) -> Self {
            n.into()
        }
        fn new_inner(n: i32) -> Self {
            Self(n)
        }
        pub fn pow<T: Into<Int>>(self, n: T) -> Self {
            let n: Int = n.into();
            let mut n = n.0;
            assert!(n >= 0);
            let mut res = StaticModInt::new(1);
            let mut x = self;
            while n != 0 {
                if n & 1 == 1 {
                    res *= x;
                }
                n /= 2;
                x *= x;
            }
            res
        }
        pub fn inv(self) -> Self {
            self.pow((MOD - 2) as u64)
        }
    }

    impl<T: Into<Int>> From<T> for StaticModInt {
        fn from(t: T) -> Self {
            let n: Int = t.into();
            let n = (n.0 % MOD as i64) as i32;
            if n < 0 {
                Self::new_inner(n + MOD)
            } else {
                Self::new_inner(n)
            }
        }
    }

    impl<T: Into<StaticModInt>> std::ops::Add<T> for StaticModInt {
        type Output = Self;
        fn add(self, rhs: T) -> Self::Output {
            let mut tmp = self.0;
            let t: StaticModInt = rhs.into();
            tmp += t.0;
            if tmp >= MOD {
                tmp -= MOD;
            }
            debug_assert!((0..MOD).contains(&tmp));
            Self(tmp)
        }
    }

    impl<T: Into<StaticModInt>> std::ops::AddAssign<T> for StaticModInt {
        fn add_assign(&mut self, rhs: T) {
            *self = *self + rhs.into()
        }
    }

    impl<T: Into<StaticModInt>> std::ops::Sub<T> for StaticModInt {
        type Output = Self;
        fn sub(self, rhs: T) -> Self::Output {
            let mut tmp = self.0;
            let t: StaticModInt = rhs.into();
            tmp -= t.0;
            if tmp < 0 {
                tmp += MOD;
            }
            debug_assert!((0..MOD).contains(&tmp));
            Self(tmp)
        }
    }

    impl<T: Into<StaticModInt>> std::ops::SubAssign<T> for StaticModInt {
        fn sub_assign(&mut self, rhs: T) {
            *self = *self - rhs.into();
        }
    }

    impl<T: Into<StaticModInt>> std::ops::Mul<T> for StaticModInt {
        type Output = Self;
        fn mul(self, rhs: T) -> Self::Output {
            let mut tmp = self.0 as i64;
            let t: StaticModInt = rhs.into();
            tmp *= t.0 as i64;
            if tmp >= MOD as i64 {
                tmp %= MOD as i64;
            }
            let tmp = tmp as i32;
            debug_assert!((0..MOD).contains(&tmp));
            Self(tmp)
        }
    }

    impl<T: Into<StaticModInt>> std::ops::MulAssign<T> for StaticModInt {
        fn mul_assign(&mut self, rhs: T) {
            *self = *self * rhs.into();
        }
    }

    impl<T: Into<StaticModInt>> std::ops::Div<T> for StaticModInt {
        type Output = Self;
        fn div(self, rhs: T) -> Self::Output {
            let t: StaticModInt = rhs.into();
            self * t.inv()
        }
    }

    impl<T: Into<StaticModInt>> std::ops::DivAssign<T> for StaticModInt {
        fn div_assign(&mut self, rhs: T) {
            *self = *self / rhs.into();
        }
    }

    /// 二項係数を高速に計算するテーブルを作成する
    /// 構築 O(N)
    /// クエリ O(1)
    /// メモリ O(N)
    pub struct CombTable {
        fac: Vec<ModInt>,
        f_inv: Vec<ModInt>,
    }

    impl CombTable {
        /// O(N)で構築
        pub fn new<T: Into<Int>>(n: T) -> Self {
            let n: Int = n.into();
            assert!(n.0 >= 0);
            let n = n.0 as usize;
            let mut fac = vec![ModInt::new(1); n + 1];
            let mut f_inv = vec![ModInt::new(1); n + 1];
            let mut inv = vec![ModInt::new(1); n + 1];
            inv[0] = ModInt::new(0);
            for i in 2..=n {
                fac[i] = fac[i - 1] * i;
                inv[i] =
                    ModInt::new(MOD) - inv[(MOD % i as i32) as usize] * ModInt::new(MOD / i as i32);
                f_inv[i] = f_inv[i - 1] * inv[i];
            }
            Self { fac, f_inv }
        }
        /// nCkをO(1)で計算
        pub fn comb<T1: Into<Int>, T2: Into<Int>>(&self, n: T1, k: T2) -> ModInt {
            let n: Int = n.into();
            let k: Int = k.into();
            assert!(n.0 >= 0);
            assert!(k.0 >= 0);
            let n = n.0 as usize;
            let k = k.0 as usize;
            if n < k {
                return ModInt::new(0);
            }
            self.fac[n] * (self.f_inv[k] * self.f_inv[n - k])
        }
    }

    #[derive(Copy, Clone, Ord, PartialOrd, Eq, PartialEq, Debug)]
    pub struct Int(pub i64);
    macro_rules! impl_int_from {($ ($ t : ty ) ,* ) => {$ (impl From < Int > for $ t {fn from (t : Int ) -> $ t {t . 0 as $ t } } ) * } ; }
    impl_int_from!(i8, i16, i32, i64, u8, u16, u32, u64, isize, usize);
    macro_rules! impl_int_into {($ ($ t : ty ) ,* ) => {$ (impl Into < Int > for $ t {fn into (self ) -> Int {Int (self as i64 ) } } ) * } ; }
    impl_int_into!(i8, i16, i32, i64, u8, u16, u32, u64, isize, usize);
}

fn main() {
    let mut io = IO::new();
    let n = io.next_usize();
    let k = io.next_usize();
    let mut a = io.next_vec::<usize>(n);
    a.sort();
    let a = rle(&a);
    let m = a.len();
    let mut sum = vec![0; m + 1];
    for i in 0..m {
        sum[i + 1] = a[i].1 + sum[i];
    }

    let mut dp = vec![vec![ModInt::new(0); n * (n - 1) / 2 + 1]; n + 1];
    dp[0][0] += 1;
    for i in 0..m {
        for j in 0..=n * (n - 1) / 2 {
            if dp[i][j] == ModInt::new(0) { continue; }

            let mut dp2 = vec![vec![vec![ModInt::new(0); sum[i] * a[i].1 + 1]; sum[i] + 1]; a[i].1 + 1];
            dp2[0][0][0] += 1;
            for k in 0..a[i].1 {
                for l in 0..=sum[i] {
                    for s in 0..=sum[i] * a[i].1 {
                        let tmp = dp2[k][l][s];
                        if tmp == ModInt::new(0) { continue; }
                        for t in l..=sum[i] {
                            dp2[k + 1][t][s + t] += tmp;
                        }
                    }
                }
            }

            // eprintln!("{:?}", dp2);

            let mut cnt = vec![ModInt::new(0); sum[i] * a[i].1 + 1];

            for s in 0..=sum[i] * a[i].1 {
                for l in 0..=sum[i] {
                    cnt[s] += dp2[a[i].1][l][s];
                }
            }

            let tmp = dp[i][j];
            for s in 0..=sum[i] * a[i].1 {
                dp[i + 1][j + s] += tmp * cnt[s];
            }
        }
    }

    // for i in 0..=m {
    //     eprintln!("{:?}", dp[i]);
    // }

    io.println(dp[m][k]);
}

pub mod basic {
    pub const U_INF: u64 = (1 << 60) + (1 << 30);
    pub const I_INF: i64 = (1 << 60) + (1 << 30);
    pub const INF: usize = (1 << 60) + (1 << 30);

    pub struct IO {
        iter: std::str::SplitAsciiWhitespace<'static>,
        buf: std::io::BufWriter<std::io::StdoutLock<'static>>,
    }

    impl Default for IO {
        fn default() -> Self {
            Self::new()
        }
    }

    impl IO {
        pub fn new() -> Self {
            use std::io::*;
            let mut input = String::new();
            std::io::stdin().read_to_string(&mut input).unwrap();
            let input = Box::leak(input.into_boxed_str());
            let out = Box::new(stdout());
            IO {
                iter: input.split_ascii_whitespace(),
                buf: BufWriter::new(Box::leak(out).lock()),
            }
        }
        pub fn next_str(&mut self) -> &str {
            self.iter.next().unwrap()
        }
        pub fn read<T: std::str::FromStr>(&mut self) -> T
            where
                <T as std::str::FromStr>::Err: std::fmt::Debug,
        {
            self.iter.next().unwrap().parse().unwrap()
        }
        pub fn next_usize(&mut self) -> usize {
            self.read()
        }
        pub fn next_uint(&mut self) -> u64 {
            self.read()
        }
        pub fn next_int(&mut self) -> i64 {
            self.read()
        }
        pub fn next_float(&mut self) -> f64 {
            self.read()
        }
        pub fn next_chars(&mut self) -> std::str::Chars {
            self.next_str().chars()
        }
        pub fn next_vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T>
            where
                <T as std::str::FromStr>::Err: std::fmt::Debug,
        {
            (0..n).map(|_| self.read()).collect::<Vec<_>>()
        }
        pub fn print<T: std::fmt::Display>(&mut self, t: T) {
            use std::io::Write;
            write!(self.buf, "{}", t).unwrap();
        }
        pub fn println<T: std::fmt::Display>(&mut self, t: T) {
            self.print(t);
            self.print("\n");
        }
        pub fn print_iter<T: std::fmt::Display, I: Iterator<Item=T>>(
            &mut self,
            mut iter: I,
            sep: &str,
        ) {
            if let Some(v) = iter.next() {
                self.print(v);
                for vi in iter {
                    self.print(sep);
                    self.print(vi);
                }
            }
            self.print("\n");
        }
        pub fn flush(&mut self) {
            use std::io::Write;
            self.buf.flush().unwrap();
        }
    }
}
0