けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

エクサウィザーズ 2019 D - Modulo Operations (600 点)

楽しい問題だった!!!

問題へのリンク

問題概要

すぬけ君は黒板と  N 個の整数からなる集合  S を持っています。すぬけ君は黒板に整数  X を書いたのち、以下の操作を  N 回行います。

  •  S から要素を 1 つ選んで取り除く。
  • その後、現在黒板に書かれた数を  x S から取り除かれた整数を  y として、黒板に書かれた数を  x \pmod y に書き換える。

 S から要素を取り除く順序は  N! 通りのそれぞれの場合について、 N 回の操作後に黒板に書かれている数を求め、その総和を  10^{9}+7 で割ったあまりを求めてください。

制約

  •  1 \le N \le 200
  •  S_i, X \le 10^{5}

考えたこと

まず、「 N! 通りの順列それぞれについての〜の総和を求めよ」という設定の問題に対して、われわれが使えるテクノロジーがあんまりない!!!!!!!

  • なんかうまい順序見つけてまとめて DP

とかくらいしかない感じ。「〜の最小値を求めよ」とかだったらフローがありうるけど、 10^{9} + 7 で割ったあまりを求めるタイプの問題でフローも考えづらい。。。

そうすると結局は、


順列をいい感じにまとめ上げて数え上げるような DP


というのを探さざるをえないことになる。

問題の構造を見る

今回の問題で色々手を動かして見えて来ることは、

  • 例えば  7 で割ったあまりをとる操作を行った後に、 11 のような  7 より大きい数で割ったあまりをとっても値は変化しない

ということ。これはかなり強い性質で、例えば

11, 19, 6, 8, 4, 13

という列に対してあまりを取る操作をするのは、

11, 6, 4

という列に対してあまりを取る操作をするのと同じことになる。これはいかにも活用できそうな構造である。

順列を走査する DP の代表: 挿入 DP

 N! 通りの順列をすべて調べ上げる DP として代表的なのは

  • bitDP (今回は制約が  N \le 200 なので無理)
  • 挿入 DP
  • 箱根駅伝みたいな DP

あたりがあると思う。今回は挿入 DP がマッチする感じ。考え方としては

  • 最初の  i+1 個の順列は、最初の  i 個の順列に対して、 i+1 番目の要素をどこかに挿入したものである

という見方をする。

3, 1, 2, 5, 4

のような 5 個の要素の順列があったら、6 個の要素の順列は「6」の挿入箇所をすべて試すことで全部調べることができる。

6, 3, 1, 2, 5, 4
3, 6, 1, 2, 5, 4
3, 1, 6, 2, 5, 4
3, 1, 2, 6, 5, 4
3, 1, 2, 5, 6, 4
3, 1, 2, 5, 4, 6

という感じ。こういう発想をすると解ける典型的な DP として EDPC の以下の問題がある:

atcoder.jp

今回の問題について

今回の問題では以上の考え方に加えて、 S をあらかじめソートしておくことにする。そうするとすごく考えやすい。

例えば  S をあらかじめソートして

5, 6, 11, 13, 22

としておいて、最初の 4 個について 24 通りの順列についての総和がわかっているとき、22 を挿入する方法は実質 2 通りしかなくて

  • 22 を先頭に挿入するとき
  • 22 を先頭以外に挿入するとき

前者は特別扱いして考える必要があるものの、後者は挿入された 22 は結局無視されることになる。以上の考察を基にして

  • dp[ i ][ x ] := スタート時点での整数が  x であるときに、最初の  i 個についての順列すべてを考えたときに得られる値の総和

とすると

  • dp[ 0 ][ x ] = x
  • dp[ i + 1 ][ x ] = dp[ i ][ x % s[ i ]] + i × dp[ i ][ x ]

という風になる。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MOD = 1000000007;

int main() {
    int N, X; cin >> N >> X;
    vector<int> S(N);
    for (int i = 0; i < N; ++i) cin >> S[i];
    sort(S.begin(), S.end());
    vector<vector<long long> > dp(N+1, vector<long long>(X+1, 0));
    for (int x = 0; x <= X; ++x) dp[0][x] = x;
    for (int i = 0; i < N; ++i) {
        for (int x = 0; x <= X; ++x) {
            dp[i+1][x] += dp[i][x % S[i]]; dp[i+1][x] %= MOD;
            dp[i+1][x] += dp[i][x] * i % MOD; dp[i+1][x] %= MOD;
        }
    }
    cout << dp[N][X] << endl;
}