結果

問題 No.1397 Analog Graffiti
ユーザー akakimidoriakakimidori
提出日時 2021-02-15 12:23:07
言語 Rust
(1.77.0)
結果
AC  
実行時間 15 ms / 10,000 ms
コード長 4,472 bytes
コンパイル時間 1,755 ms
コンパイル使用メモリ 161,068 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-30 06:01:02
合計ジャッジ時間 2,947 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 15 ms
4,376 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 15 ms
4,376 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 7 ms
4,380 KB
testcase_08 AC 7 ms
4,376 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 14 ms
4,376 KB
testcase_12 AC 4 ms
4,380 KB
testcase_13 AC 14 ms
4,380 KB
testcase_14 AC 14 ms
4,376 KB
testcase_15 AC 7 ms
4,376 KB
testcase_16 AC 4 ms
4,376 KB
testcase_17 AC 14 ms
4,376 KB
testcase_18 AC 14 ms
4,380 KB
testcase_19 AC 2 ms
4,376 KB
testcase_20 AC 1 ms
4,376 KB
testcase_21 AC 1 ms
4,376 KB
testcase_22 AC 10 ms
4,380 KB
testcase_23 AC 7 ms
4,380 KB
testcase_24 AC 1 ms
4,376 KB
testcase_25 AC 7 ms
4,380 KB
testcase_26 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

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);
}
0