Project Euler 684 Inverse Digit Sum

問題

projecteuler.net

解法

各桁の数の和がxとなるような最小の整数 s(x) は必ず一番上の桁以外は全て9となる。
よって s(x) は以下のようになる。

s(x) の和 S(x) を考える。
S(20)=1074だが、これは以下のようにして求まる。

s(1)    =           1
...
s(9)    =           9
s(10)   =       1   9
s(11)   =       2   9
...
s(18)   =       9   9
s(19)   =   1   9   9
s(20)   =   2   9   9

これは式変形の力によって以下の式で求まる。

よって S(x) が O(1) で求まるので、あとは各フィボナッチ数について計算すれば良い。

use self::mod_int::ModInt;

const MOD: u128 = 1e9 as u128 + 7;

fn main() {
    let mut f: Vec<u128> = vec![0, 1];
    let mut ans = ModInt(0);
    for i in 2..91 {
        let fi = f[i - 1] + f[i - 2];
        f.push(fi);
        ans += big_s2(fi);
    }
    println!("{}", ans.0);
}

fn big_s(x: u128) -> u128 {
    let nines = x / 9;
    let remain = x % 9;
    let mut sum = 0;
    sum += (remain + 1) * remain / 2;
    let mut upper = remain;
    for _ in 0..nines {
        sum *= 10;
        sum += upper * 9;
        sum += (9 + 1) * 9 / 2;
        upper += 9;
    }
    sum
}

fn big_s2(x: u128) -> ModInt<u128> {
    let nines = x / 9;
    let sum = if nines > 0 {
        let r = nines - 1;
        (ModInt(2).pow(r + 2) * ModInt(5).pow(r + 1) - 5 - ModInt(3) * r) * 3
    } else {
        ModInt(0)
    };
    let remain = x % 9;
    let head =
        (ModInt(10).pow(nines) - 1) * remain + ModInt(10).pow(nines) * (remain + 1) * remain / 2;
    sum + head
}

pub mod mod_int {
    use super::MOD;
    use std::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Sub, SubAssign};

    type Num = u128;

    #[derive(Clone, Copy)]
    pub struct ModInt<T: Copy + Clone>(pub T);

    impl Add<ModInt<Num>> for ModInt<Num> {
        type Output = ModInt<Num>;
        fn add(self, rhs: ModInt<Num>) -> ModInt<Num> {
            self + rhs.0
        }
    }

    impl Add<Num> for ModInt<Num> {
        type Output = ModInt<Num>;
        fn add(self, rhs: Num) -> ModInt<Num> {
            let mut t = rhs + self.0;
            if t >= MOD {
                t = t - MOD;
            }
            ModInt(t)
        }
    }

    impl Sub<Num> for ModInt<Num> {
        type Output = ModInt<Num>;
        fn sub(self, rhs: Num) -> ModInt<Num> {
            let rhs = if rhs >= MOD { rhs % MOD } else { rhs };
            let value = if self.0 < rhs { self.0 + MOD } else { self.0 };
            ModInt(value - rhs)
        }
    }

    impl Sub<ModInt<Num>> for ModInt<Num> {
        type Output = ModInt<Num>;
        fn sub(self, rhs: ModInt<Num>) -> ModInt<Num> {
            self - rhs.0
        }
    }

    impl AddAssign<Num> for ModInt<Num> {
        fn add_assign(&mut self, other: Num) {
            *self = *self + other;
        }
    }
    impl AddAssign<ModInt<Num>> for ModInt<Num> {
        fn add_assign(&mut self, other: ModInt<Num>) {
            *self = *self + other;
        }
    }

    impl SubAssign<Num> for ModInt<Num> {
        fn sub_assign(&mut self, other: Num) {
            *self = *self - other;
        }
    }

    impl SubAssign<ModInt<Num>> for ModInt<Num> {
        fn sub_assign(&mut self, other: ModInt<Num>) {
            *self = *self - other;
        }
    }

    impl Div<Num> for ModInt<Num> {
        type Output = ModInt<Num>;
        fn div(self, rhs: Num) -> ModInt<Num> {
            self * ModInt(rhs).pow(MOD - 2)
        }
    }

    impl Div<ModInt<Num>> for ModInt<Num> {
        type Output = ModInt<Num>;
        fn div(self, rhs: ModInt<Num>) -> ModInt<Num> {
            self / rhs.0
        }
    }

    impl DivAssign<Num> for ModInt<Num> {
        fn div_assign(&mut self, rhs: Num) {
            *self = *self / rhs
        }
    }
    impl DivAssign<ModInt<Num>> for ModInt<Num> {
        fn div_assign(&mut self, rhs: ModInt<Num>) {
            *self = *self / rhs
        }
    }

    impl Mul<ModInt<Num>> for ModInt<Num> {
        type Output = ModInt<Num>;

        fn mul(self, rhs: ModInt<Num>) -> ModInt<Num> {
            self * rhs.0
        }
    }
    impl Mul<Num> for ModInt<Num> {
        type Output = ModInt<Num>;

        fn mul(self, rhs: Num) -> ModInt<Num> {
            let t = (self.0 * rhs) % MOD;
            ModInt(t)
        }
    }

    impl MulAssign<Num> for ModInt<Num> {
        fn mul_assign(&mut self, rhs: Num) {
            *self = *self * rhs;
        }
    }

    impl MulAssign<ModInt<Num>> for ModInt<Num> {
        fn mul_assign(&mut self, rhs: ModInt<Num>) {
            *self = *self * rhs;
        }
    }

    impl ModInt<Num> {
        pub fn pow(self, e: Num) -> ModInt<Num> {
            let mut result = ModInt(1);
            let mut cur = self;
            let mut e = e;
            while e > 0 {
                if e & 1 == 1 {
                    result *= cur;
                }
                e >>= 1;
                cur *= cur;
            }
            result
        }
    }
}