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

https://atcoder.jp/contests/exawizards2019/tasks/exawizards2019_d

前提知識

• 動的計画法

解説

https://atcoder.jp/contests/exawizards2019/submissions/4770817

DPテクを組み合わせる。
「2. 選択するものを最初にソートしておくと、DPできたり、状態を同一化できたりする」
「3. 状態が全部必要ないので状態数が削減できる」

テク2の方は、Sを降順ソートして、大きい方から使うかどうか決めていくことにする。
ある2つのS[i], S[j]を考えた場合にS[i]<S[j]ならば、S[i]を取ってからS[j]を取るとS[j]によって数は変化しないので、 より変化があり、状態を分けて考える必要がある降順に選択することを考えるためである。

テク3の方は、Xからmod計算を繰り返していくが、modの重要な性質が1つあり
ある数に対してmodを取ると、全く同じになるか、半分未満の数になる
これにより、操作中に現れるxの数の種類はそんなに多くないんじゃないかという仮定が立つ。 よって、状態数をすべて見るのではなく、でてきたものだけ処理するようにする。

これで準備が整った。
dp[i][x] := i-1番目まで取り出す順序が確定していて、黒板にxと書かれている組合せ
これが求まればdp[N][x]×xが答えになる。
dp[i][x]からの遷移は、次に取り出す数S[nxt]を決める。すると、S[i], ... , S[nxt-1]の数はこの先どこにおいても、数に変化は無いことになる。そのため、先に置いてしまおう。 今後選択する数がrest=N-1-nxt個あり、どこにおいても変化が無い数の個数がnotuse=nxt-iであるとき、P(rest+notuse, notuse)通りのどこにおいても変化の無い数の置き方があるので、それをかけて遷移先に足す。 計算しても無駄な状態は計算しないように枝刈りすると通る。

int N, X, S[201];
mint dp[201][101010];
Comb<mint, 1010> com;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> X;
    rep(i, 0, N) cin >> S[i];
    sort(S, S + N, greater<int>());
 
    dp[0][X] = 1;
    rep(i, 0, N) rep(x, 1, X + 1) if(0 < dp[i][x].get()){
        rep(nxt, i, N) {
            int notuse = nxt - i;
            int xx = x % S[nxt];
            int rest = N - 1 - nxt;
            dp[nxt + 1][xx] += dp[i][x] * com.aPb(rest + notuse, notuse);
        }
    }
 
    mint ans = 0;
    rep(x, 1, X + 1) ans += dp[N][x] * x;
    cout << ans << endl;
}