エクサウィザーズ 2019 D問題：Modulo Operations

問題. Modulo Operations

$N$ 個の相異なる自然数からなる集合 $S$ と自然数 $X$ が与えられる．初期値を $X$ として次の操作を $N$ 回行う． $S$ から任意に要素 $S_i$ を1つ選んで取り除き，現在の値 $x$ を $x \bmod S_i$ に更新する． $S$ の任意の取り除き方によって得られる $N$ 回の操作後の値の総和を求めよ．

制約： $1 \le N \le 200$ ，　 $1 \le S_i, X \le 10^5$

$S$ は降順に整列していると仮定する．すなわち， $S_1 > S_2 > \cdots > S_N$ とする． $f(i, x)$ を初期値が $x$ で部分集合 $S' = \{S_i, S_{i+1}, \ldots, S_N\}$ に対して得られる答えである総和とする． $S_i$ は $S'$ の最大値なので，選択する順番によって $S_i$ が $N - i + 1$ 回の操作後の値に影響を与えない．まず $S_i$ が初期値 $x$ で操作後の値に影響を与える可能性がある場合を考える．それは， $S_i$ が初めに選択されるときのみで，このときの総和は $f(i + 1, \, x \bmod S_i)$ となる．次に， $S_i$ が操作後の値に影響を与えない場合であるが，それは $S_i$ が2番目以降に選択されるときである．このときの総和は $f(i + 1, x)$ に対して $S_i$ が2番目以降に選択される $i$ 通りの方法がありうるので $i \times f(i + 1, x)$ となる．したがって，
　　 $f(i, x) = f(i + 1, \, x \bmod S_i) + i \times f(i + 1, x)$
となる．
以上で， $S$ を降順にソートするのに $O(N \log N)$ 時間で，上の実装をメモ化再帰で $O(N X)$ 時間で実装できるので，全体で $O(N \log N + N X)$ 時間で求まる．

計算時間： $O(N \log N + N X)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

constexpr ll MOD = 1e9 + 7;

ll N, X;
vector<ll> s;
vector<vector<ll>> memo;

ll Rec(int idx, ll x) {
    if (idx == N) return x;
    if (memo[idx][x] != -1) return memo[idx][x];

    ll &res = memo[idx][x];
    res = Rec(idx + 1, x % s[idx]) % MOD;
    (res += Rec(idx + 1, x) * (N - idx - 1)) %= MOD;

    return res;
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    cin >> N >> X;
    s.resize(N);
    for (auto &s_i : s) cin >> s_i;
    sort(s.begin(), s.end(), greater<ll>());

    memo.resize(N, vector<ll>(X + 1, -1));
    cout << Rec(0, X) << endl;

    return 0;
}