#1178569 (Rust) No.1269 I hate Fibonacci Number

• 問題: No.1269 I hate Fibonacci Number
• ユーザー: hayatroid
• 提出日時: 2026-08-23 17:40:10
• 言語: Rust (1.94.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 178 ms / 3,000 ms
• コード長: 3,298 bytes
• コンパイル時間: 10,796 ms
• コンパイル使用メモリ: 197,508 KB
• 実行使用メモリ: 6,272 KB
• 最終ジャッジ日時: 2026-08-23 17:40:55
• 合計ジャッジ時間: 5,286 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
sample	AC * 3
other	AC * 36

ソースコード

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

use proconio::input;

fn main() {
    input! {
        n: usize,
        l: u64,
        r: u64,
    }
    let mut ws = Vec::new();
    let (mut x, mut y) = (1, 1);
    while x <= r {
        if l <= x {
            ws.push(x.to_string().into_bytes());
        }
        (x, y) = (y, x + y);
    }
    let dfa = Not(ContainsAny::new(&ws));
    println!("{}", count(dfa, b'0'..=b'9', n) - 1);
}

const MOD: u64 = 1_000_000_007;

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 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 ContainsAny {
    next: Vec<[usize; 10]>,
    accept: Vec<bool>,
}

impl ContainsAny {
    fn new(ws: &[Vec<u8>]) -> Self {
        let (mut next, mut accept) = (vec![[0; 10]], vec![false]);
        for w in ws {
            let mut q = 0;
            for &c in w {
                let c = (c - b'0') as usize;
                if next[q][c] == 0 {
                    next[q][c] = next.len();
                    next.push([0; 10]);
                    accept.push(false);
                }
                q = next[q][c];
            }
            accept[q] = true;
        }
        let mut fail = vec![0; next.len()];
        let mut bfs = VecDeque::new();
        for q in next[0] {
            if q != 0 {
                bfs.push_back(q);
            }
        }
        while let Some(q) = bfs.pop_front() {
            accept[q] |= accept[fail[q]];
            for c in 0..10 {
                if next[q][c] != 0 {
                    fail[next[q][c]] = next[fail[q]][c];
                    bfs.push_back(next[q][c]);
                } else {
                    next[q][c] = next[fail[q]][c];
                }
            }
        }
        for q in 0..accept.len() {
            if accept[q] {
                next[q] = [q; 10];
            }
        }
        ContainsAny { next, accept }
    }
}

impl Dfa for ContainsAny {
    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]
    }
}