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

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

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

AtCoder AtCoder600点 挿入DP DP 数え上げ問題 順列の数え上げ 数列 数学(整数問題) 探索順序を工夫して解く 操作:modをとる 黄色diff ARC-D

楽しい問題だった！！！

問題へのリンク

問題概要

すぬけ君は黒板と 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;
}