エクサウィザーズ 2019 D - Modulo Operations
問題
解法
解説にあるとおり、ある数が使われた後、その数より大きい数を使ったとしても剰余には影響しないので、大きい数から順番に見ていって数列に詰めていくことを考える。
i番目(0 <= i < n )に大きい数 x_i を数列に詰める時、空いている場所は (n-i) ヶ所ある。この (n-i) ヶ所のうち一番前を除く (n-i-1) ヶ所のどこかに詰めると、x_i より小さい数が x_i の前に来ることになり、 x_i は剰余に対して影響しなくなる。一番前に詰めると x_i の前にある数は必ず x_i より大きくなるので、剰余に影響するようになる。
コード
const MOD: usize = 1e9 as usize + 7; fn main() { let s = std::io::stdin(); let mut sc = Scanner { stdin: s.lock() }; let n: usize = sc.read(); let x: usize = sc.read(); let mut s: Vec<usize> = sc.vec(n); s.sort(); s.reverse(); let mut dp = vec![0; x + 1]; dp[x] = 1; for i in 0..n { let mut next = vec![0; x + 1]; for j in 0..(x + 1) { // unused next[j] += dp[j] * (n - 1 - i); next[j] %= MOD; // used next[j % s[i]] += dp[j]; next[j % s[i]] %= MOD; } dp = next; } let mut ans = 0; for i in 0..s[n - 1] { ans += dp[i] * i; ans %= MOD; } println!("{}", ans); } pub struct Scanner<R> { stdin: R, } impl<R: std::io::Read> Scanner<R> { pub fn read<T: std::str::FromStr>(&mut self) -> T { use std::io::Read; let buf = self .stdin .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r') .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r') .collect::<Vec<_>>(); unsafe { std::str::from_utf8_unchecked(&buf) } .parse() .ok() .expect("Parse error.") } pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> { (0..n).map(|_| self.read()).collect() } pub fn chars(&mut self) -> Vec<char> { self.read::<String>().chars().collect() } }