日々ｄｒｄｒする人のメモ

今日も明日もｄｒｄｒ

トップ > ProCon > AtCoder: エクサウィザーズ2019 - D問題: Modulo Operations

AtCoder: エクサウィザーズ2019 - D問題: Modulo Operations

ProCon AtCoder

これ解くのに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}から順に以下のように伝搬し、各通り数の和を求める。

  1. {y_{i+1}}を後回しにする場合 (つまり、整数 {X}に何も影響しないケース)
    • {dp[i][k] \leftarrow dp[i+1][k] \times i}
  2. {y_{i+1}}を適用する場合 (整数 {X}に影響を与えうるケース)
    • {dp[i][k \text{ mod } y_i] \leftarrow dp[i+1][k]}
    • (もしくは {0 \le k < y_i}について {\displaystyle 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通り)


そして、最後に {\displaystyle \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)