https://kyopro.hateblo.jp/entry/2019/04/01/092445

問題. 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;
}

解説が理解できなかった．動的計画法よりもメモ化再帰の方が理解しやすいというよりは，動的計画法に上手く変換できなかったので時間のあるときに考える．本番では惜しいところまで考察できていたのに残念．

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

問題. Modulo Operations

解法．動的計画法