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

問題のリンク

D - Modulo Operations

考察

少し自分の手で操作をしてみて気づくことは、S[i] < S[j] を満たすとき、S[i]、S[j] の順番に取り除くと、S[i]をとり除いた後、黒板に書かれた数はS[i] 未満になっているので、S[j] を取り除いても黒板の数は変わらないことがわかる。

サンプル2 で、13 22 6 11 5 の順番に取り出したとする。このとき、22、11 はそれ未満の数字を取り出した後に取り出されているので、黒板の数字を変えない。そのため、無かったことにして良く、13 6 5 を取り出した、というパターンと同じになる。この{13, 6, 5} をeffective なset と呼ぶ。例えば、13 6 5 22 11 の順に取り出した場合もeffective なset は{13, 6, 5} で、最終的に黒板に書かれている数も同じになる。

そこで、S[i] を降順に見ていき、effective なset に入れるか、入れないか、を決めていく（降順に見ていくとS[i]はその時点では最小なので、入れることができる）。ただし、最小の値、S[n-1]は必ずeffective なset に入れることとする。また、黒板に書かれている数字も持っておき、effective なset に値が入る度に更新していく。

dp[i][j] := S[i-1]まで見たとき、黒板に書かれている数字がj であるような場合の数。

ここで、S[i] をeffective なset に入れる、入れないとは実際に選び出す順番とどう関係しているかを見ていく。実はこれは前から順に、その数字を何番目に取り出すかを決めていっているのである。effective なset に入れるということは、その時点で最も早い順目にその数字を取り出すことを決める、ということであり、入れないということは、それ以外の順目で取り出すことを決める、ということである。

上と同じように、サンプル2 で見ていくと、22 をeffective なset に入れないとすると、22 を取り出す順番を1 番目以外に決めるということであり、n-1 = 4 通りある。13 をeffective なset に入れるとすると、13 をそのときに決まっていない順番のうち最も早い順番で取り出す、ということであり、22 をeffective なset に入れていれば、2 番目であるし、入れていないなら、1 番目である。どちらの場合も1 通りであることがわかる。

このように考えると、dp table の遷移は、

dp[i+1][j % S[i] ] += dp[i][j];  // そのときの一番早い位置に決まるので1 通り
dp[i+1][j] += dp[i][j] * ( n - i - 1 );  // すでにi 個は取り出される順番が決まっていて、最も早い順目は避けるのでn - i - 1 通り。

となる。これで、O(NX)で解けてめでたし、めでたし。

実装

#include <iostream>
#include <algorithm>
#include <vector>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }
typedef long long ll;
const ll MOD=1e+9+7;
struct mint{
  ll x;
  mint(ll x=0):x(x%MOD){}
  mint& operator+=(const mint a){
    if((x+=a.x)>=MOD) x-=MOD;
    return *this;
  }
  mint& operator-=(const mint a){
    if((x += MOD-a.x)>=MOD) x-=MOD;
    return *this;
  }
  mint& operator*=(const mint a){
    (x*=a.x)%=MOD;
    return *this;
  }
  mint operator+(const mint a) const{
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const{
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const{
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const{
    if(!t) return 1;
    mint a = pow(t>>1);
    a*=a;
    if(t&1) a*=*this;
    return a;
  }
  
  //for prime mod
  mint inv() const{
    return pow(MOD-2);
  }
  mint& operator/=(const mint a){
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const{
    mint res(*this);
    return res/=a;
  }
};


int main()
{
  int n, x; cin >> n >> x;
  vector<int> s(n);
  rep(i,n) cin >> s[i];

  sort(s.begin(), s.end(), [](int a, int b)-> bool{
                 return a > b;
               });

  vector<mint> modinv(n+1);
  rep1(i,n) modinv[i] = (mint)1 / (mint)i;
  
  vector<vector<mint>> dp(n+1, vector<mint>(x+1));
  dp[0][x].x = 1;
  rep(i,n) {
    rep(j,x+1) {
      dp[i+1][j % s[i]] += dp[i][j];
      dp[i+1][j]        += dp[i][j] * (mint)(n - 1 - i);
    }
  }

  mint res;
  rep(j,x+1) res += dp[n][j]*(mint)j;
  cout << res.x << "\n";
  
  
  return 0;
}