結果

問題 No.2983 Christmas Color Grid (Advent Calender ver.)
ユーザー akakimidori
提出日時 2024-12-08 11:07:44
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 30 ms / 3,340 ms
コード長 21,835 bytes
コンパイル時間 14,472 ms
コンパイル使用メモリ 379,444 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-08 11:08:14
合計ジャッジ時間 16,470 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 64
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused import: `std::io::Write`
 --> src/main.rs:2:5
  |
2 | use std::io::Write;
  |     ^^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: unnecessary parentheses around assigned value
   --> src/main.rs:239:21
    |
239 |             let v = (rand() % 100 < 50);
    |                     ^                 ^
    |
    = note: `#[warn(unused_parens)]` on by default
help: remove these parentheses
    |
239 -             let v = (rand() % 100 < 50);
239 +             let v = rand() % 100 < 50;
    |

warning: unused variable: `at`
  --> src/main.rs:27:9
   |
27 |     let at = |bit: usize, i: usize, j: usize| bit >> pos(i, j) & 1 == 1;
   |         ^^ help: if this is intentional, prefix it with an underscore: `_at`
   |
   = note: `#[warn(unused_variables)]` on by default

warning: unused variable: `conn`
   --> src/main.rs:100:11
    |
100 |     for ((conn, size), geta) in dp {
    |           ^^^^ help: if this is intentional, prefix it with an underscore: `_conn`

warning: unused variable: `size`
   --> src/main.rs:100:17
    |
100 |     for ((conn, size), geta) in dp {
    |                 ^^^^ help: if this is intentional, prefix it with an underscore: `_size`

warning: type alias `Set` is never used
 --> src/main.rs:5:6
  |
5 | type Set<T> = BTreeSet<T>;
  |      ^^^
  |
  = note: `#[warn(dead_code)]` on by default

warning: type alias `Deque` is never used
 --> src/main.rs:6:6
  |
6 | type Deque<T> = VecDeque<T>;
  |      ^^^^^

warning: function `naive` is never used
   --> src/main.rs:108:4
    |
108 | fn naive() {
    |    ^^^^^

warning: function `rand_memory` is never used
   --> src/main.rs:743:4
    |
743 | fn rand_memory() -> usize {
    |    ^^^^^^^^^^^

warning: function `rand` is never used
   --> src/main.rs:747:4
    |
747 | fn rand() -> usize {
    |    ^^^^

warning: function `shuffle` is never used
   --> src/main.rs:760:4
    |
760 | fn shuffle<T>(a: &mut [T]) {
    |    ^^^^^^^

ソースコード

diff #
プレゼンテーションモードにする

use std::collections::*;
use std::io::Write;
type Map<K, V> = BTreeMap<K, V>;
type Set<T> = BTreeSet<T>;
type Deque<T> = VecDeque<T>;
use modint::*;
type M = ModInt<StaticMod>;
fn main() {
    input! {
        h: usize,
        w: usize,
        k: u64,
        m: u32,
    }
    StaticMod::set_modulo(m);
    let pow = (0..=(h * w)).map(|i| M::from(i).pow(k)).collect::<Vec<_>>();
    let mut h = h;
    let mut w = w;
    if h < w {
        std::mem::swap(&mut h, &mut w);
    }
    let (h, w) = (h, w);
    let pos = |i, j| i * w + j;
    let at = |bit: usize, i: usize, j: usize| bit >> pos(i, j) & 1 == 1;
    let pc = precalc::Precalc::new(1000);
    let mut dp = Map::new();
    const W: usize = 5;
    dp.insert(([0; W], [0; W]), (M::one(), M::zero()));
    for i in 0..=h {
        let mut next = Map::new();
        for ((state, size), geta) in dp {
            let mut dsu = DSU::new(2 * w);
            let up = if i == h { 1 } else { 1 << w };
            for bit in 0..up {
                dsu.init();
                let mut memo = [w; W];
                for (i, s) in state.iter().enumerate().filter(|s| *s.1 > 0) {
                    if memo[*s] != w {
                        dsu.unite(memo[*s], i);
                    }
                    memo[*s] = i;
                }
                let mut s = [0; 2 * W];
                for i in 0..w {
                    if state[i] > 0 && dsu.root(i) == i {
                        s[i] = size[state[i]];
                    }
                    s[w + i] = bit >> i & 1;
                }
                for i in 0..w {
                    if state[i] > 0 && bit >> i & 1 == 1 {
                        dsu.unite(i, i + w).map(|(p, c)| s[p] += s[c]);
                    }
                    if i > 0 && bit >> (i - 1) & 3 == 3 {
                        dsu.unite(i + w - 1, i + w).map(|(p, c)| s[p] += s[c]);
                    }
                }
                let mut rem = [false; 2 * W];
                for i in 0..w {
                    if bit >> i & 1 == 1 {
                        rem[dsu.root(i + w)] = true;
                    }
                }
                let mut geta = geta;
                let mut used = [false; 2 * W];
                for i in 0..w {
                    if state[i] > 0 && !rem[dsu.root(i)] && !used[dsu.root(i)] {
                        used[dsu.root(i)] = true;
                        geta.1 += pow[size[state[i]]] * geta.0;
                    }
                }
                let mut map = [0; 2 * W];
                let mut id = 1;
                let mut next_conn = [0; W];
                let mut next_size = [0; W];
                for i in 0..w {
                    if bit >> i & 1 == 1 {
                        let root = dsu.root(i + w);
                        if map[root] == 0 {
                            map[root] = id;
                            id += 1;
                        }
                        next_conn[i] = map[root];
                        next_size[map[root]] = s[root];
                    }
                }
                let po = next
                    .entry((next_conn, next_size))
                    .or_insert((M::zero(), M::zero()));
                po.0 += geta.0;
                po.1 += geta.1;
            }
        }
        dp = next;
    }
    let mut ans = M::zero();
    for ((conn, size), geta) in dp {
        ans += geta.1;
    }
    ans *= M::new(2).inv().pow((h * w) as u64);
    ans *= (1..=(h * w)).fold(M::zero(), |s, a| s + pc.inv(a));
    println!("{}", ans);
}
fn naive() {
    input! {
        h: usize,
        w: usize,
        k: u64,
        m: u32,
    }
    let pos = |i, j| i * w + j;
    let at = |bit: usize, i: usize, j: usize| bit >> pos(i, j) & 1 == 1;
    StaticMod::set_modulo(m);
    let pc = precalc::Precalc::new(1000);
    let mut size = vec![0; h * w];
    let mut hist = vec![M::zero(); h * w + 1];
    for bit in 1usize..(1 << (h * w)) {
        let mut dsu = DSU::new(h * w);
        size.fill(0);
        for (i, s) in size.iter_mut().enumerate() {
            *s = bit >> i & 1;
        }
        for i in 1..h {
            for j in 0..w {
                if at(bit, i, j) && at(bit, i - 1, j) {
                    if let Some((p, c)) = dsu.unite(pos(i - 1, j), pos(i, j)) {
                        size[p] += size[c];
                    }
                }
            }
        }
        for i in 0..h {
            for j in 1..w {
                if at(bit, i, j) && at(bit, i, j - 1) {
                    if let Some((p, c)) = dsu.unite(pos(i, j - 1), pos(i, j)) {
                        size[p] += size[c];
                    }
                }
            }
        }
        let mut sum = M::zero();
        for i in 0..(h * w) {
            if i == dsu.root(i) {
                sum += M::from(size[i]).pow(k);
            }
        }
        hist[bit.count_ones() as usize] += sum;
    }
    println!("{:?}", hist);
    let mut ans = M::zero();
    for i in 1..hist.len() {
        for j in 0..=(h * w - i) {
            let mut val = hist[i];
            val *= pc.inv(2).pow((i + j) as u64);
            val *= pc.comb(h * w - i, j);
            val *= pc.comb(h * w, i + j).inv();
            val *= pc.inv(h * w - i - j + 1);
            ans += val;
        }
    }
    println!("{}", ans);
    let mut ans = M::zero();
    ans += M::new(3) * M::new(8).inv();
    ans += M::new(6) * (M::new(4 * 3 * 2).inv() + M::new(8).inv());
    ans += M::new(3) * (M::new(18).inv() + M::new(24).inv() + M::new(8).inv());
    println!("{}", ans);
    let mut ans = M::zero();
    for b in 1usize..3usize.pow((h * w) as u32) {
        let mut dsu = DSU::new(h * w);
        let mut free = 0;
        let mut b = b;
        let mut bit = 0;
        let mut size = vec![0; h * w];
        for i in 0..h {
            for j in 0..w {
                let k = b % 3;
                b /= 3;
                if k == 0 {
                    free += 1;
                } else if k == 1 {
                    size[pos(i, j)] = 1;
                    bit |= 1 << pos(i, j);
                }
            }
        }
        for i in 1..h {
            for j in 0..w {
                if at(bit, i, j) && at(bit, i - 1, j) {
                    if let Some((p, c)) = dsu.unite(pos(i - 1, j), pos(i, j)) {
                        size[p] += size[c];
                    }
                }
            }
        }
        for i in 0..h {
            for j in 1..w {
                if at(bit, i, j) && at(bit, i, j - 1) {
                    if let Some((p, c)) = dsu.unite(pos(i, j - 1), pos(i, j)) {
                        size[p] += size[c];
                    }
                }
            }
        }
        let mut sum = M::zero();
        for i in 0..(h * w) {
            if i == dsu.root(i) {
                sum += M::new(size[i]).pow(k);
            }
        }
        sum *= pc.ifact(h * w);
        sum *= pc.fact(h * w - free) * pc.fact(free);
        sum *= pc.inv(free + 1);
        sum *= M::new(2).pow((h * w - free) as u64).inv();
        ans += sum;
    }
    println!("{}", ans);
    for i in 0..100 {
        for j in 1..100 {
            let v = M::new(i) * M::new(j).inv();
            if v.get() == 249561091 {
                println!("{} {}", i, j);
            }
        }
    }
    println!("{}", M::new(13) * M::new(6).inv());
    let mut ans = 0.0;
    let it = 10000000;
    for _ in 0..it {
        let mut dsu = DSU::new(h * w);
        let mut dp = vec![0; h * w];
        let mut state = vec![vec![0; w]; h];
        let mut p = (0..(h * w)).collect::<Vec<_>>();
        shuffle(&mut p);
        for (i, p) in p.iter().enumerate() {
            let v = (rand() % 100 < 50);
            if v {
                let (a, b) = (*p / w, *p % w);
                state[a][b] = 1;
                dp[*p] = 1;
                for &(dx, dy) in [(1, 0), (0, 1), (!0, 0), (0, !0)].iter() {
                    let (x, y) = (a + dx, b + dy);
                    if x < h && y < w && state[x][y] == 1 {
                        if let Some((p, c)) = dsu.unite(pos(a, b), pos(x, y)) {
                            dp[p] += dp[c];
                        }
                    }
                }
            }
            let mut sum = 0;
            for i in 0..(h * w) {
                if i == dsu.root(i) {
                    sum += dp[i];
                }
            }
            ans += sum as f64 / (h * w - i) as f64;
        }
    }
    ans /= it as f64;
    println!("{:.7}", ans);
}
// ---------- begin input macro ----------
// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[macro_export]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}
#[macro_export]
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}
#[macro_export]
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, bytes) => {
        read_value!($iter, String).bytes().collect::<Vec<u8>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
// ---------- end input macro ----------
mod modint {
    use std::marker::*;
    use std::ops::*;
    pub trait Modulo {
        fn modulo() -> u32;
        fn im() -> u64;
        fn reduce(z: u64) -> u32 {
            let x = (z as u128 * Self::im() as u128 >> 64) as u32;
            let mut v = z as u32 - x * Self::modulo();
            if v >= Self::modulo() {
                v += Self::modulo();
            }
            v
        }
    }
    pub struct StaticMod;
    static mut STATIC_MOD: u32 = 0;
    static mut STATIC_MOD_IM: u64 = 0;
    impl Modulo for StaticMod {
        fn modulo() -> u32 {
            unsafe { STATIC_MOD }
        }
        fn im() -> u64 {
            unsafe { STATIC_MOD_IM }
        }
    }
    #[allow(dead_code)]
    impl StaticMod {
        pub fn set_modulo(p: u32) {
            unsafe {
                STATIC_MOD = p;
                STATIC_MOD_IM = (!0u64 / p as u64) + 1;
            }
        }
    }
    pub struct ModInt<T>(u32, PhantomData<T>);
    impl<T> Clone for ModInt<T> {
        fn clone(&self) -> Self {
            ModInt::build(self.0)
        }
    }
    impl<T> Copy for ModInt<T> {}
    impl<T: Modulo> Add for ModInt<T> {
        type Output = ModInt<T>;
        fn add(self, rhs: Self) -> Self::Output {
            let mut d = self.0 + rhs.0;
            if d >= T::modulo() {
                d -= T::modulo();
            }
            Self::build(d)
        }
    }
    impl<T: Modulo> AddAssign for ModInt<T> {
        fn add_assign(&mut self, rhs: Self) {
            *self = *self + rhs;
        }
    }
    impl<T: Modulo> Sub for ModInt<T> {
        type Output = ModInt<T>;
        fn sub(self, rhs: Self) -> Self::Output {
            let mut d = self.0 - rhs.0;
            if self.0 < rhs.0 {
                d += T::modulo();
            }
            Self::build(d)
        }
    }
    impl<T: Modulo> SubAssign for ModInt<T> {
        fn sub_assign(&mut self, rhs: Self) {
            *self = *self - rhs;
        }
    }
    impl<T: Modulo> Mul for ModInt<T> {
        type Output = ModInt<T>;
        fn mul(self, rhs: Self) -> Self::Output {
            Self::build(T::reduce(self.0 as u64 * rhs.0 as u64))
        }
    }
    impl<T: Modulo> MulAssign for ModInt<T> {
        fn mul_assign(&mut self, rhs: Self) {
            *self = *self * rhs;
        }
    }
    impl<T: Modulo> Neg for ModInt<T> {
        type Output = ModInt<T>;
        fn neg(self) -> Self::Output {
            if self.0 == 0 {
                Self::zero()
            } else {
                Self::build(T::modulo() - self.0)
            }
        }
    }
    impl<T: Modulo> std::fmt::Display for ModInt<T> {
        fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result {
            write!(f, "{}", self.get())
        }
    }
    impl<T: Modulo> std::fmt::Debug for ModInt<T> {
        fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result {
            write!(f, "{}", self.get())
        }
    }
    impl<T: Modulo> Default for ModInt<T> {
        fn default() -> Self {
            Self::zero()
        }
    }
    impl<T: Modulo> std::str::FromStr for ModInt<T> {
        type Err = std::num::ParseIntError;
        fn from_str(s: &str) -> Result<Self, Self::Err> {
            let val = s.parse::<u32>()?;
            Ok(ModInt::new(val))
        }
    }
    impl<T: Modulo> From<usize> for ModInt<T> {
        fn from(val: usize) -> ModInt<T> {
            ModInt::new_unchecked((val % T::modulo() as usize) as u32)
        }
    }
    impl<T: Modulo> From<u64> for ModInt<T> {
        fn from(val: u64) -> ModInt<T> {
            ModInt::new_unchecked((val % T::modulo() as u64) as u32)
        }
    }
    impl<T: Modulo> From<i64> for ModInt<T> {
        fn from(val: i64) -> ModInt<T> {
            let m = T::modulo() as i64;
            ModInt::new((val % m + m) as u32)
        }
    }
    #[allow(dead_code)]
    impl<T> ModInt<T> {
        fn build(d: u32) -> Self {
            ModInt(d, PhantomData)
        }
        pub fn zero() -> Self {
            Self::build(0)
        }
        pub fn is_zero(&self) -> bool {
            self.0 == 0
        }
    }
    #[allow(dead_code)]
    impl<T: Modulo> ModInt<T> {
        pub fn new_unchecked(d: u32) -> Self {
            Self::build(d)
        }
        pub fn new(d: u32) -> Self {
            Self::new_unchecked(d % T::modulo())
        }
        pub fn one() -> Self {
            Self::new_unchecked(1)
        }
        pub fn get(&self) -> u32 {
            self.0
        }
        pub fn pow(&self, mut n: u64) -> Self {
            let mut t = Self::one();
            let mut s = *self;
            while n > 0 {
                if n & 1 == 1 {
                    t *= s;
                }
                s *= s;
                n >>= 1;
            }
            t
        }
        pub fn inv(&self) -> Self {
            assert!(!self.is_zero());
            self.pow((T::modulo() - 2) as u64)
        }
    }
}
// ---------- begin Precalc ----------
mod precalc {
    use super::modint::*;
    #[allow(dead_code)]
    pub struct Precalc<T> {
        inv: Vec<ModInt<T>>,
        fact: Vec<ModInt<T>>,
        ifact: Vec<ModInt<T>>,
    }
    #[allow(dead_code)]
    impl<T: Modulo> Precalc<T> {
        pub fn new(n: usize) -> Precalc<T> {
            let mut inv = vec![ModInt::one(); n + 1];
            let mut fact = vec![ModInt::one(); n + 1];
            let mut ifact = vec![ModInt::one(); n + 1];
            for i in 2..(n + 1) {
                fact[i] = fact[i - 1] * ModInt::new_unchecked(i as u32);
            }
            ifact[n] = fact[n].inv();
            if n > 0 {
                inv[n] = ifact[n] * fact[n - 1];
            }
            for i in (1..n).rev() {
                ifact[i] = ifact[i + 1] * ModInt::new_unchecked((i + 1) as u32);
                inv[i] = ifact[i] * fact[i - 1];
            }
            Precalc {
                inv: inv,
                fact: fact,
                ifact: ifact,
            }
        }
        pub fn inv(&self, n: usize) -> ModInt<T> {
            assert!(n > 0);
            self.inv[n]
        }
        pub fn fact(&self, n: usize) -> ModInt<T> {
            self.fact[n]
        }
        pub fn ifact(&self, n: usize) -> ModInt<T> {
            self.ifact[n]
        }
        pub fn perm(&self, n: usize, k: usize) -> ModInt<T> {
            if k > n {
                return ModInt::zero();
            }
            self.fact[n] * self.ifact[n - k]
        }
        pub fn comb(&self, n: usize, k: usize) -> ModInt<T> {
            if k > n {
                return ModInt::zero();
            }
            self.fact[n] * self.ifact[k] * self.ifact[n - k]
        }
    }
}
// ---------- end Precalc ----------
//---------- begin union_find ----------
pub struct DSU {
    p: Vec<i32>,
}
impl DSU {
    pub fn new(n: usize) -> DSU {
        assert!(n < std::i32::MAX as usize);
        DSU { p: vec![-1; n] }
    }
    pub fn init(&mut self) {
        self.p.iter_mut().for_each(|p| *p = -1);
    }
    pub fn root(&self, mut x: usize) -> usize {
        assert!(x < self.p.len());
        while self.p[x] >= 0 {
            x = self.p[x] as usize;
        }
        x
    }
    pub fn same(&self, x: usize, y: usize) -> bool {
        assert!(x < self.p.len() && y < self.p.len());
        self.root(x) == self.root(y)
    }
    pub fn unite(&mut self, x: usize, y: usize) -> Option<(usize, usize)> {
        assert!(x < self.p.len() && y < self.p.len());
        let mut x = self.root(x);
        let mut y = self.root(y);
        if x == y {
            return None;
        }
        if self.p[x] > self.p[y] {
            std::mem::swap(&mut x, &mut y);
        }
        self.p[x] += self.p[y];
        self.p[y] = x as i32;
        Some((x, y))
    }
    pub fn parent(&self, x: usize) -> Option<usize> {
        assert!(x < self.p.len());
        let p = self.p[x];
        if p >= 0 {
            Some(p as usize)
        } else {
            None
        }
    }
    pub fn sum<F>(&self, mut x: usize, mut f: F) -> usize
    where
        F: FnMut(usize),
    {
        while let Some(p) = self.parent(x) {
            f(x);
            x = p;
        }
        x
    }
    pub fn size(&self, x: usize) -> usize {
        assert!(x < self.p.len());
        let r = self.root(x);
        (-self.p[r]) as usize
    }
}
//---------- end union_find ----------
// ---------- begin super slice ----------
pub trait SuperSlice {
    type Item;
    fn lower_bound(&self, key: &Self::Item) -> usize
    where
        Self::Item: Ord;
    fn lower_bound_by<F>(&self, f: F) -> usize
    where
        F: FnMut(&Self::Item) -> std::cmp::Ordering;
    fn lower_bound_by_key<K, F>(&self, key: &K, f: F) -> usize
    where
        K: Ord,
        F: FnMut(&Self::Item) -> K;
    fn upper_bound(&self, key: &Self::Item) -> usize
    where
        Self::Item: Ord;
    fn upper_bound_by<F>(&self, f: F) -> usize
    where
        F: FnMut(&Self::Item) -> std::cmp::Ordering;
    fn upper_bound_by_key<K, F>(&self, key: &K, f: F) -> usize
    where
        K: Ord,
        F: FnMut(&Self::Item) -> K;
    fn next_permutation(&mut self) -> bool
    where
        Self::Item: Ord;
    fn next_permutation_by<F>(&mut self, f: F) -> bool
    where
        F: FnMut(&Self::Item, &Self::Item) -> std::cmp::Ordering;
    fn prev_permutation(&mut self) -> bool
    where
        Self::Item: Ord;
}
impl<T> SuperSlice for [T] {
    type Item = T;
    fn lower_bound(&self, key: &Self::Item) -> usize
    where
        T: Ord,
    {
        self.lower_bound_by(|p| p.cmp(key))
    }
    fn lower_bound_by<F>(&self, mut f: F) -> usize
    where
        F: FnMut(&Self::Item) -> std::cmp::Ordering,
    {
        self.binary_search_by(|p| f(p).then(std::cmp::Ordering::Greater))
            .unwrap_err()
    }
    fn lower_bound_by_key<K, F>(&self, key: &K, mut f: F) -> usize
    where
        K: Ord,
        F: FnMut(&Self::Item) -> K,
    {
        self.lower_bound_by(|p| f(p).cmp(key))
    }
    fn upper_bound(&self, key: &Self::Item) -> usize
    where
        T: Ord,
    {
        self.upper_bound_by(|p| p.cmp(key))
    }
    fn upper_bound_by<F>(&self, mut f: F) -> usize
    where
        F: FnMut(&Self::Item) -> std::cmp::Ordering,
    {
        self.binary_search_by(|p| f(p).then(std::cmp::Ordering::Less))
            .unwrap_err()
    }
    fn upper_bound_by_key<K, F>(&self, key: &K, mut f: F) -> usize
    where
        K: Ord,
        F: FnMut(&Self::Item) -> K,
    {
        self.upper_bound_by(|p| f(p).cmp(key))
    }
    fn next_permutation(&mut self) -> bool
    where
        T: Ord,
    {
        self.next_permutation_by(|a, b| a.cmp(b))
    }
    fn next_permutation_by<F>(&mut self, mut f: F) -> bool
    where
        F: FnMut(&Self::Item, &Self::Item) -> std::cmp::Ordering,
    {
        use std::cmp::Ordering::*;
        if let Some(x) = self.windows(2).rposition(|a| f(&a[0], &a[1]) == Less) {
            let y = self.iter().rposition(|b| f(&self[x], b) == Less).unwrap();
            self.swap(x, y);
            self[(x + 1)..].reverse();
            true
        } else {
            self.reverse();
            false
        }
    }
    fn prev_permutation(&mut self) -> bool
    where
        T: Ord,
    {
        self.next_permutation_by(|a, b| a.cmp(b).reverse())
    }
}
// ---------- end super slice ----------
fn rand_memory() -> usize {
    Box::into_raw(Box::new("I hope this is a random number")) as usize
}
fn rand() -> usize {
    static mut X: usize = 0;
    unsafe {
        if X == 0 {
            X = rand_memory();
        }
        X ^= X << 13;
        X ^= X >> 17;
        X ^= X << 5;
        X
    }
}
fn shuffle<T>(a: &mut [T]) {
    for i in 1..a.len() {
        let p = rand() % (i + 1);
        a.swap(i, p);
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0