#1178551 (Rust) No.2867 NOT FOUND 404 Again

• 問題: No.2867 NOT FOUND 404 Again
• ユーザー: hayatroid
• 提出日時: 2026-08-23 16:56:32
• 言語: Rust (1.94.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 2,835 ms / 3,000 ms
• コード長: 3,183 bytes
• コンパイル時間: 8,795 ms
• コンパイル使用メモリ: 193,260 KB
• 実行使用メモリ: 6,272 KB
• 最終ジャッジ日時: 2026-08-23 16:57:33
• 合計ジャッジ時間: 60,048 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
sample	AC * 2
other	AC * 18

ソースコード

use std::{cmp::Ordering, collections::HashMap, hash::Hash};

use proconio::{input, marker::Bytes};

fn main() {
    input! {
        n: Bytes
    }
    let dfa = Not(Contains::new(b"404"));
    println!("{}", count(And(dfa, Le(&n)), b'0'..=b'9', n.len()) - 1);
}

const MOD: u64 = 998_244_353;

fn count<A>(dfa: A, sigma: impl Iterator<Item = A::Alphabet> + Clone, len: usize) -> u64
where
    A: Dfa,
    A::State: Eq + Hash,
{
    let mut dp = HashMap::new();
    dp.insert(dfa.init(), 1);
    for _ in 0..len {
        let mut ndp = HashMap::new();
        for (q, v) in dp {
            for c in sigma.clone() {
                let e = ndp.entry(dfa.next(&q, &c)).or_insert(0);
                *e = (*e + v) % MOD;
            }
        }
        dp = ndp;
    }
    dp.iter()
        .filter_map(|(q, v)| dfa.accept(q).then_some(v))
        .fold(0, |sum, v| (sum + v) % MOD)
}

trait Dfa {
    type State;
    type Alphabet;
    fn init(&self) -> Self::State;
    fn next(&self, q: &Self::State, c: &Self::Alphabet) -> Self::State;
    fn accept(&self, q: &Self::State) -> bool;
}

struct And<A, B>(A, B);
impl<A: Dfa, B: Dfa<Alphabet = A::Alphabet>> Dfa for And<A, B> {
    type State = (A::State, B::State);
    type Alphabet = A::Alphabet;
    fn init(&self) -> Self::State {
        (self.0.init(), self.1.init())
    }
    fn next(&self, q: &Self::State, c: &Self::Alphabet) -> Self::State {
        (self.0.next(&q.0, c), self.1.next(&q.1, c))
    }
    fn accept(&self, q: &Self::State) -> bool {
        self.0.accept(&q.0) && self.1.accept(&q.1)
    }
}

struct Not<A>(A);
impl<A: Dfa> Dfa for Not<A> {
    type State = A::State;
    type Alphabet = A::Alphabet;
    fn init(&self) -> Self::State {
        self.0.init()
    }
    fn next(&self, q: &Self::State, c: &Self::Alphabet) -> Self::State {
        self.0.next(q, c)
    }
    fn accept(&self, q: &Self::State) -> bool {
        !self.0.accept(q)
    }
}

struct Le<'a>(&'a [u8]);
impl Dfa for Le<'_> {
    type State = (Ordering, usize);
    type Alphabet = u8;
    fn init(&self) -> Self::State {
        (Ordering::Equal, 0)
    }
    fn next(&self, q: &Self::State, c: &Self::Alphabet) -> Self::State {
        (q.0.then(c.cmp(&self.0[q.1])), q.1 + 1)
    }
    fn accept(&self, q: &Self::State) -> bool {
        q.0.is_le()
    }
}

struct Contains {
    next: Vec<[usize; 10]>,
    accept: Vec<bool>,
}

impl Contains {
    fn new(w: &[u8]) -> Self {
        let n = w.len();
        let (mut next, mut accept) = (vec![[0; 10]; n + 1], vec![false; n + 1]);
        let mut fail = vec![0; n + 1];
        for q in 0..n {
            next[q] = next[fail[q]];
            fail[q + 1] = next[fail[q]][(w[q] - b'0') as usize];
            next[q][(w[q] - b'0') as usize] = q + 1;
        }
        (next[n], accept[n]) = ([n; 10], true);
        Contains { next, accept }
    }
}

impl Dfa for Contains {
    type State = usize;
    type Alphabet = u8;
    fn init(&self) -> Self::State {
        0
    }
    fn next(&self, q: &Self::State, c: &Self::Alphabet) -> Self::State {
        self.next[*q][(c - b'0') as usize]
    }
    fn accept(&self, q: &Self::State) -> bool {
        self.accept[*q]
    }
}