結果

問題 No.1397 Analog Graffiti
ユーザー akakimidoriakakimidori
提出日時 2021-02-15 12:23:07
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 16 ms / 10,000 ms
コード長 4,472 bytes
コンパイル時間 13,309 ms
コンパイル使用メモリ 402,784 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-22 23:59:49
合計ジャッジ時間 14,722 ms
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

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

//---------- 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 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) {
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;
}
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;
}
}
//---------- end union_find ----------
fn read() -> (usize, usize, usize) {
let mut s = String::new();
std::io::stdin().read_line(&mut s).unwrap();
let a = s
.trim()
.split_whitespace()
.flat_map(|s| s.parse::<usize>())
.collect::<Vec<_>>();
(a[0], a[1], a[2])
}
fn dfs(bit: usize, k: usize, id: usize, v: &mut Vec<usize>, state: &mut Vec<Vec<usize>>) {
if k == v.len() {
state.push(v.clone());
return;
}
if bit >> k & 1 == 0 {
dfs(bit, k + 1, id, v, state);
} else if k > 0 && bit >> (k - 1) & 1 == 1 {
v[k] = v[k - 1];
dfs(bit, k + 1, id, v, state);
} else {
for i in 1..=(id + 1) {
v[k] = i;
dfs(bit, k + 1, id.max(i), v, state);
}
}
}
fn valid(a: &[usize], b: &[usize]) -> bool {
if b.iter().all(|b| *b == 0) {
return a.iter().all(|a| *a <= 1);
}
let mut ok = true;
for (a, b) in a.windows(2).zip(b.windows(2)) {
ok &= a[0] == a[1] || b[0] == b[1] || (a[0] == 0 && b[0] == 0) || (a[1] == 0 && b[1] == 0);
}
let c = a.len();
let mut dsu = DSU::new(2 * c);
for l in 0..c {
let mut zero = false;
let mut hole = false;
for r in (l + 1)..c {
zero |= a[r] == 0;
hole |= a[r] == 0 && b[r] == 0;
if a[l] == a[r] && a[l] > 0 {
dsu.unite(l, r);
ok &= !zero || hole;
}
}
if l > 0 && b[l] == b[l - 1] && b[l] > 0 {
dsu.unite(l + c, l - 1 + c);
}
if a[l] > 0 && b[l] > 0 {
dsu.unite(l, l + c);
}
}
for i in 0..c {
if a[i] > 0 {
ok &= (0..c).any(|k| b[k] > 0 && dsu.same(i, k + c));
}
}
for i in 0..c {
for j in 0..i {
if b[i] > 0 && b[j] > 0 {
ok &= dsu.same(i + c, j + c) ^ (b[i] != b[j]);
}
}
}
ok
}
fn main() {
let (r, c, n) = read();
let mut state = vec![];
for i in 0..(1 << c) {
dfs(i, 0, 0, &mut vec![0; c], &mut state);
}
let mut trans = vec![vec![]; state.len()];
for (trans, a) in trans.iter_mut().zip(state.iter()) {
for (to, b) in state.iter().enumerate() {
if valid(&a, &b) {
let mut x = vec![0; c + 2];
x[1..=c].copy_from_slice(a);
let mut y = vec![0; c + 2];
y[1..=c].copy_from_slice(b);
let mut add = 0;
for (a, b) in x.windows(2).zip(y.windows(2)) {
if (a[0] > 0) ^ (a[1] > 0) ^ (b[0] > 0) ^ (b[1] > 0) {
add += 1;
}
}
trans.push((to, add));
}
}
}
const MOD: u64 = 998_244_353;
let mut dp = vec![vec![0u64; n + 1]; state.len()];
dp[0][0] = 1;
let mut ans = 0;
for _ in 0..=r {
let mut next = vec![vec![0u64; n + 1]; state.len()];
for (trans, dp) in trans.iter().zip(dp.iter()) {
for (i, dp) in dp.iter().enumerate().filter(|p| *p.1 > 0) {
for &(u, x) in trans.iter() {
if i + x <= n {
next[u][i + x] += *dp;
}
}
}
}
dp = next;
dp.iter_mut().flatten().for_each(|dp| *dp %= MOD);
ans += dp[0][n];
dp[0].iter_mut().for_each(|dp| *dp = 0);
dp[0][0] = 1;
}
ans %= MOD;
println!("{}", ans);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0