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

• 問題: No.1269 I hate Fibonacci Number
• ユーザー: hayatroid
• 提出日時: 2026-08-25 10:58:24
• 言語: Rust (1.94.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 176 ms / 3,000 ms
• コード長: 3,800 bytes
• コンパイル時間: 4,361 ms
• コンパイル使用メモリ: 199,212 KB
• 実行使用メモリ: 6,272 KB
• 最終ジャッジ日時: 2026-08-25 10:58:34
• 合計ジャッジ時間: 8,711 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

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

ソースコード

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

use proconio::input;

// 0. 決定性有限オートマトン
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;
}

// 1. ContainsAny(ws) は ws のどれかがつく数を認識するオートマトン
struct ContainsAny {
    next: Vec<[usize; 10]>,
    accept: Vec<bool>,
}
impl ContainsAny {
    fn new(ws: &[Vec<u8>]) -> Self {
        // 1-1. ws の trie をつくる
        let mut next = vec![[0; 10]];
        let mut accept = 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;
        }
        // 1-2. failure 辺を張る
        let mut fail = vec![0; next.len()];
        let mut bfs = VecDeque::new();
        for c in 0..10 {
            if next[0][c] != 0 {
                bfs.push_back(next[0][c]);
            }
        }
        while let Some(q) = bfs.pop_front() {
            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];
                }
            }
            accept[q] |= accept[fail[q]];
        }
        // 1-3. 受理状態に留まるようにする
        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]
    }
}

// 2. Not(a) は a が認識しない数を認識するオートマトン
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)
    }
}

const MOD: u64 = 1_000_000_007;

// 3. count(a, Σ, n) は a が認識する言語と Σ^n の共通部分を 10^9 + 7 で割った余りで数える
fn count<A, S>(dfa: A, sigma: S, len: usize) -> u64
where
    A: Dfa,
    A::State: Eq + Hash,
    S: Iterator<Item = A::Alphabet> + Clone,
{
    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)
}

// 4. Just Do It !!!!
fn main() {
    input!(n: usize, l: u64, r: u64);
    let mut ws = vec![];
    let (mut x, mut y) = (1, 1);
    while x < l {
        (x, y) = (y, x + y);
    }
    while x <= r {
        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) + MOD - 1) % MOD);
}