結果
問題 | No.1397 Analog Graffiti |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
//---------- 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);}