#1178531 (Rust) No.220 世界のなんとか2

• 問題: No.220 世界のなんとか2
• ユーザー: hayatroid
• 提出日時: 2026-08-23 15:05:14
• 言語: Rust (1.94.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 0 ms / 1,000 ms
• コード長: 2,208 bytes
• コンパイル時間: 1,743 ms
• コンパイル使用メモリ: 192,648 KB
• 実行使用メモリ: 6,272 KB
• 最終ジャッジ日時: 2026-08-23 15:05:21
• 合計ジャッジ時間: 3,288 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
other	AC * 19

ソースコード

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

use proconio::input;

fn main() {
    input! {
        p: usize,
    }
    let solve = |p| {
        let mut v = vec![b'0'; p + 1];
        v[0] = b'1';
        count(Or(MultipleOf(3), Seen(b'3')), p, b'0'..=b'9')
    };
    println!("{}", solve(p) - solve(0));
}

fn count<A>(dfa: A, len: usize, sigma: impl Iterator<Item = A::Alphabet> + Clone) -> 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() {
                *ndp.entry(dfa.next(&q, &c)).or_insert(0) += v;
            }
        }
        dp = ndp;
    }
    let mut res = 0;
    for (q, v) in dp {
        if dfa.accept(&q) {
            res += v;
        }
    }
    res
}

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 Or<A, B>(A, B);
impl<A: Dfa, B: Dfa<Alphabet = A::Alphabet>> Dfa for Or<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 MultipleOf(u64);
impl Dfa for MultipleOf {
    type State = u64;
    type Alphabet = u8;
    fn init(&self) -> Self::State {
        0
    }
    fn next(&self, q: &Self::State, c: &Self::Alphabet) -> Self::State {
        (q * 10 + (c - b'0') as u64) % self.0
    }
    fn accept(&self, q: &Self::State) -> bool {
        *q == 0
    }
}

struct Seen(u8);
impl Dfa for Seen {
    type State = bool;
    type Alphabet = u8;
    fn init(&self) -> Self::State {
        false
    }
    fn next(&self, q: &Self::State, c: &Self::Alphabet) -> Self::State {
        *q || *c == self.0
    }
    fn accept(&self, q: &Self::State) -> bool {
        *q
    }
}