結果
| 問題 |
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]) {
| ^^^^^^^
ソースコード
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);
}
}