Submission #36066421

---

Source Code Expand

use proconio::input;

fn main() {
    input! {
        n: u128,
    }

    println!("{}", rec(n));
}

fn rec(n: u128) -> u128 {
    if n == 0 {
        return 1;
    }
    
    let mut tmp = n;
    let mut i = 1;
    loop {
        if tmp / 3 == 0 {
            break;
        }
        tmp /= 3;
        i += 1;
    }

    let mut result = 0u128;
    for j in 0..=i {
        let mut arg = 1;

        for _ in 0..j {
            arg = arg * 2;
        }

        for _ in j..i {
            arg = arg * 3;
        }

        result += cmp(i, j) * rec(n / arg);
    }

    return result;
}

fn cmp(n: u128, k: u128) -> u128 {
    let k = if (n / 2) < k { n - k } else { k };
    let mut result = 1;
    for i in 0..k {
        result = result * (n - i) / (i + 1);
    }

    return result;
}

Submission Info

Judge Result