Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

【Educational DP-S Digit Sum】足してDの倍数 = mod Dで足して0

S - Digit Sum

問題

K以下の数字のうち、各桁の数を足し合わせた和がDの倍数なものは何個あるか?

制約: K=1010000, D=100

方針

10000桁について、全通り調べていたら910000ルートなので宇宙が滅びるまで終わりません。

次に、K以下でDの倍数のものを全部調べて、和がそれらになるものを足し合わせるという方針を考えますが、これも微妙です。

制約から、D=100というのを使って問題を圧縮することが求められてるような気がします。

正しいアプローチは、足してDというのは、mod Dで和が0ということです。例えば、Dが3とします。すると、12も48も3の倍数なのですが、これは、どちらも(1 mod 3)(2 mod 3)だからです。これなら計算量的に解けそうなことがわかります。

しかし実装上は考えるべき点があります。それは、例えばKが323だとして、これは先頭を2に落とせば下2桁はどちらも9以下で取り放題ということがわかります。しかし、先頭が3のままでは下二桁は9をとれません。これをうまくケアする必要があります。

私が考えた実装は、

0-323 = 000-299 + 300-319 + 32[0-3]

と分解することです。こうすると、「どこかの桁を一つ落としてそれ以降全部9以下」というのを足していけばよいことになり、「長さLの9で作れる0 mod Dは何個か」という簡単な問題をDPで解けば良いことになります。連続9より前の和は、累積和を計算すればO(1)になります。

実装

fn solve() {
    input!{
        K:chars,
        D:usize,
    }

    let mut k = vec![];
    for c in K {
        let mut cc = String::new();
        cc.push(c);
        let x: usize = cc.parse().unwrap();
        k.push(x);
    }
    // L連続の9
    // nines[L][mod D]
    let mut nines = dvec![0; k.len()+1,D];
    for j in 0..10 {
        nines[1][j%D] += 1;
    }
    for i in 1..k.len() { // 10000
        for j in 0..10 { // 10
            for d in 0..D { // 100
                nines[i+1][(d+j)%D] += nines[i][d];
                nines[i+1][(d+j)%D] %= mo;
            }
        }
    }

    let n = k.len();
    let mut cum = CumSum1::build(&k);

    let mut sum = 0;
    for i in 0..n-1 {
        let x = k[i];
        let premod = cum.query(0,i);
        // K=3223の場合
        // 0000-2999
        // 3000-3199
        // 3200-3219
        for m in 0..x {
            let headsum = (premod+m)%D;
            sum += nines[n-(i+1)][(D-headsum)%D];
            sum %= mo;
        }
    }
    // 最後の桁
    let premod = cum.query(0,n-1)%D;
    for x in 0..k[n-1]+1 {
        if (premod+x)%D==0 {
            sum+=1;
            sum%=mo;
        }
    }
    // 000000は抜く
    // sumが0の場合がある
    println!("{}",(mo+sum-1)%mo);
}

考察

足してDの倍数が、mod Dで足して0という言い換えはわりと典型です。

あと、これは嵌ってる人が多いですが、最後に0を除くために1を引く段階になって、sum=0である問題セットが2つあります。うそーん109+7の倍数になるなんてある!?と驚きましたが、最後まで気を抜いてはならないと学びました(2時間嵌った)。ついにライブラリにModIntを追加したのでありました。