エクサウィザーズ 2019 D - Modulo Operations

問題

atcoder.jp

解法

解説にあるとおり、ある数が使われた後、その数より大きい数を使ったとしても剰余には影響しないので、大きい数から順番に見ていって数列に詰めていくことを考える。

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()
    }
}