https://atcoder.jp/contests/abc357/tasks/abc357_d
の桁数を
として、
を求めるだけですが、すぐにオーバーフローするので大変です。Fermatの小定理も使わないといけません。
// 88888888 #![allow(non_snake_case)] //////////////////// 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() } // ax = by + 1 (a, b > 0) fn linear_diophantine(a: i64, b: i64) -> Option<(i64, i64)> { if a == 1 { return Some((1, 0)) } let q = b / a; let r = b % a; if r == 0 { return None } let (x1, y1) = linear_diophantine(r, a)?; Some((-q * x1 - y1, -x1)) } fn inverse(a: i64, d: i64) -> i64 { let (x, _y) = linear_diophantine(a, d).unwrap(); if x >= 0 { x % d } else { x % d + d } } fn pow(a: i64, e: i64, d: i64) -> i64 { if e == 0 { 1 } else if e == 1 { a } else if e % 2 == 1 { a * pow(a, e-1, d) % d } else { let n = pow(a, e/2, d); n * n % d } } fn num_digits(n: i64) -> i64 { if n < 10 { 1 } else { 1 + num_digits(n/10) } } //////////////////// process //////////////////// const D: i64 = 998244353; fn F(N: i64) -> i64 { let M = num_digits(N); let A = N % D; let B = pow(10, N % (D-1) * M, D) - 1; let C = inverse(pow(10, M, D) % D - 1, D); A * B % D * C % D } fn main() { let N: i64 = read(); println!("{}", F(N)) }