use std::collections::*; use std::io::Write; type Map = BTreeMap; type Set = BTreeSet; type Deque = VecDeque; use modint::*; type M = ModInt; 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::>(); 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::>(); 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::>() }; ($iter:expr, chars) => { read_value!($iter, String).chars().collect::>() }; ($iter:expr, bytes) => { read_value!($iter, String).bytes().collect::>() }; ($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(u32, PhantomData); impl Clone for ModInt { fn clone(&self) -> Self { ModInt::build(self.0) } } impl Copy for ModInt {} impl Add for ModInt { type Output = ModInt; 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 AddAssign for ModInt { fn add_assign(&mut self, rhs: Self) { *self = *self + rhs; } } impl Sub for ModInt { type Output = ModInt; 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 SubAssign for ModInt { fn sub_assign(&mut self, rhs: Self) { *self = *self - rhs; } } impl Mul for ModInt { type Output = ModInt; fn mul(self, rhs: Self) -> Self::Output { Self::build(T::reduce(self.0 as u64 * rhs.0 as u64)) } } impl MulAssign for ModInt { fn mul_assign(&mut self, rhs: Self) { *self = *self * rhs; } } impl Neg for ModInt { type Output = ModInt; fn neg(self) -> Self::Output { if self.0 == 0 { Self::zero() } else { Self::build(T::modulo() - self.0) } } } impl std::fmt::Display for ModInt { fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result { write!(f, "{}", self.get()) } } impl std::fmt::Debug for ModInt { fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result { write!(f, "{}", self.get()) } } impl Default for ModInt { fn default() -> Self { Self::zero() } } impl std::str::FromStr for ModInt { type Err = std::num::ParseIntError; fn from_str(s: &str) -> Result { let val = s.parse::()?; Ok(ModInt::new(val)) } } impl From for ModInt { fn from(val: usize) -> ModInt { ModInt::new_unchecked((val % T::modulo() as usize) as u32) } } impl From for ModInt { fn from(val: u64) -> ModInt { ModInt::new_unchecked((val % T::modulo() as u64) as u32) } } impl From for ModInt { fn from(val: i64) -> ModInt { let m = T::modulo() as i64; ModInt::new((val % m + m) as u32) } } #[allow(dead_code)] impl ModInt { 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 ModInt { 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 { inv: Vec>, fact: Vec>, ifact: Vec>, } #[allow(dead_code)] impl Precalc { pub fn new(n: usize) -> Precalc { 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 { assert!(n > 0); self.inv[n] } pub fn fact(&self, n: usize) -> ModInt { self.fact[n] } pub fn ifact(&self, n: usize) -> ModInt { self.ifact[n] } pub fn perm(&self, n: usize, k: usize) -> ModInt { if k > n { return ModInt::zero(); } self.fact[n] * self.ifact[n - k] } pub fn comb(&self, n: usize, k: usize) -> ModInt { 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, } 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 { assert!(x < self.p.len()); let p = self.p[x]; if p >= 0 { Some(p as usize) } else { None } } pub fn sum(&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(&self, f: F) -> usize where F: FnMut(&Self::Item) -> std::cmp::Ordering; fn lower_bound_by_key(&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(&self, f: F) -> usize where F: FnMut(&Self::Item) -> std::cmp::Ordering; fn upper_bound_by_key(&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(&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 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(&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(&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(&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(&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(&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(a: &mut [T]) { for i in 1..a.len() { let p = rand() % (i + 1); a.swap(i, p); } }