競プロ典型 005

https://atcoder.jp/contests/typical90/tasks/typical90_e

入力例1で考えましょう。
1桁目を7で割った余りを考えます。そうすると、1, 4, 2が1回ずつ出てくるので、次のような母関数を考えます。

2桁目は

で、これは

と同じです。2桁で考えると、

となります。つまり、7で割り切れる2桁の数は3つです。具体的には14、49、91です。
このようにしていけば計算できますが、分割統治法を使えば速いです。4桁を考えるとこれを2桁ずつに分けて、とこれに100を掛けたを掛ければ4桁の母関数になります。

// Restricted Digits
#![allow(non_snake_case)]


//////////////////// constances ////////////////////

const D: usize = 10usize.pow(9) + 7;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}

fn pow(n: usize, e: usize, d: usize) -> usize {
    if e == 1 {
        n
    }
    else if e % 2 == 1 {
        n * pow(n, e-1, d) % d
    }
    else {
        let p = pow(n, e/2, d);
        p * p % d
    }
}


//////////////////// process ////////////////////

fn read_input() -> (i64, i64, Vec<i64>) {
    let v = read_vec();
    let (N, B) = (v[0], v[1]);
    let cs = read_vec();
    (N, B, cs)
}

fn initialize_counter(cs: &Vec<i64>, B: i64) -> Vec<usize> {
    let mut counter: Vec<usize> = vec![0; B as usize];
    for &c in cs.iter() {
        counter[(c%B) as usize] += 1
    }
    counter
}

fn mul(counter1: &Vec<usize>, counter2: &Vec<usize>, n: i64) -> Vec<usize> {
    let B = counter1.len();
    let R = pow(10, n as usize, B);
    let mut counter: Vec<usize> = vec![0; B];
    for (r1, &f1) in counter1.iter().enumerate() {
        for (r2, &f2) in counter2.iter().enumerate() {
            let r = (r1 * R + r2) % B;
            counter[r] = (counter[r] + f1 * f2) % D
        }
    }
    counter
}

fn DC(n: i64, B: i64, cs: &Vec<i64>) -> Vec<usize> {
    if n == 1 {
        initialize_counter(cs, B)
    }
    else if n % 2 == 1 {
        mul(&DC(n-1, B, cs), &initialize_counter(cs, B), 1)
    }
    else {
        let counter = DC(n/2, B, cs);
        mul(&counter, &counter, n/2)
    }
}

fn F(N: i64, B: i64, cs: Vec<i64>) -> usize {
    let counter = DC(N, B, &cs);
    counter[0]
}

fn main() {
    let (N, B, cs) = read_input();
    println!("{}", F(N, B, cs))
}