https://smijake3.hatenablog.com/entry/2019/03/31/130655

これ解くのに1時間はかかりすぎた。反省回。
atcoder.jp

問題概要

${N}$ 個の整数からなる集合 ${S}$ と整数 ${X}$ が与えられる。

この集合 ${S}$ に含まれる1つの整数 ${y}$ を取り除き、整数 ${X}$ を ${X}$ mod ${y}$ に書き換える。この操作を集合 ${S}$ が空になるまでの ${N}$ 回行う。

集合 ${S}$ の整数を取り除く順序は ${N!}$ 通り存在するが、全ての順序における最終的な整数 ${X}$ の値の総和を ${10^9 + 7}$ で割った余りで求めよ。

制約

${1 \le N \le 200}$
集合の整数: ${1 \le S_i \le 10^5}$ ( ${S_i}$ は相異なる)
${1 \le X \le 10^5}$

解法

dpをする。

集合の ${N}$ 個の整数を ${y_1 < y_2 < ... < y_N}$ とする。
まず、 ${y_i < y_j}$ となる ${i, j}$ について、 ${y_j}$ を後回しにして先に ${y_i}$ を使った場合、mod ${y_j}$ によって整数 ${X}$ は変化しない。
また、mod ${y_1}$ は必ず適用されるため、最終的な整数 ${X}$ は ${0 \le X < y_1}$ を満たす。

ここで、各 ${0 \le k < y_1}$ について、 ${N}$ 回の操作後に最終的に ${X = k}$ となる通り数を求めることを考える。

そこで以下のdpを考える。
${dp[i][k]}$ = ${y_{i+1}, y_{i+2}, ..., y_N}$ を使った(もしくは後回しにした)時点で整数 ${X}$ が ${k}$ の時の通り数

初期値は ${dp[N][X] = 1}$ とする。

dpは ${i = N}$ から順に以下のように伝搬し、各通り数の和を求める。

を後回しにする場合 (つまり、整数に何も影響しないケース)
- ${dp[i][k] \leftarrow dp[i+1][k] \times i}$
を適用する場合 (整数に影響を与えうるケース)
- ${dp[i][k \text{ mod } y_i] \leftarrow dp[i+1][k]}$
- (もしくは ${0 \le k < y_i}$ について $dp[i][k] \leftarrow \sum_{m \ge 0} dp[i+1][k + m \times y_i]$ )

${N}$ 個の要素 ${y_1, y_2, ..., y_N}$ を使う順序で並べることを考えた時、
(1)の ${\times i}$ は以下のイメージの青い箇所の ${i}$ 通りである。(2)は赤い箇所の1通りに該当する。

f:id:smijake3:20190331114310p:plain — 使う順序のイメージ
(i+1個の要素の中で ${y_{i+1}}$ を最初に使うのが1通り、それ以外がi通り)

使う順序のイメージ
(i+1個の要素の中で ${y_{i+1}}$ を最初に使うのが1通り、それ以外がi通り)

そして、最後に $\sum_{0 \le k < y_1} k \times dp[0][k]$ を計算して解とすればよい。

計算量 ${O(NX)}$ で求められる。

実装

提出コード(PyPy3): Submission #4778607 - ExaWizards 2019

N, X = map(int, input().split())
*V, = map(int, input().split())
 
MOD = 10**9 + 7
 
V.sort()
 
S = [0]*(X+1)
S[X] = 1
T = [0]*(X+1)
zeros = [0]*(X+1)
for i in range(N-1, -1, -1):
    T[:] = zeros
    for k in range(X+1):
        S[k] %= MOD
        T[k] += S[k] * i % MOD
        T[k % V[i]] += S[k]
    S, T = T, S
print(sum(k*S[k] % MOD for k in range(V[0])) % MOD)