MODNTEST - EDITORIAL

PROBLEM LINK:

Contest

Setter: debrc

Tester: mishra_roshan

Editorialist: debrc

DIFFICULTY:

Medium

PREREQUISITES:

Dynamic Programming

PROBLEM:

Given a number M and an array A of N integers, perform the following operations N number of times-

  • Pop any one integer from A
  • Replace M in the board with M%A_i (Where A_i is the popped integer).

At the end, after doing the above operations N times, the board will be left with an integer named X.
As there N! ways of removing N elements from the array A, so there can be N number of X's.
Calculate the sum of all those X's.

EXPLANATION

This problem can be easily solved using Dynamic Programming and understanding the two states.

Sort the sequence first.
Make an array of two states i.e. dp [ i ][ j ].

dp [ i ][ j ] gives us the answer to the problem when N=i and M=j.
Now, three cases can happen-

  1. Obviusly, when N=0,
    dp [ 0 ][ j ]=j,
    because nothing will get modded.

  2. Otherwise,
    dp [ i ][ j ] = dp[ i-1 ][j%A[ i ]] + dp[ i-1 ][ j ]*i
    The first sum part is when A[i] is chosen first, the second sum part is when A[i] is not chosen first.

  3. Or else, the answer remains unchanged, as doing %s[i] on number <s[i] does not yield anything.

TIME COMPLEXITY

Time complexity is O(N*M) for building the array.

SOLUTIONS:

Setter's Solution
C++
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define double long double
#define rep(i,n) for (int i=0; i<(int)(n); ++i)
#define rep1(i,n) for (int i=1; i<(int)(n); ++i)
#define repeq(i,n) for (int i=0; i<=(int)(n); ++i)
#define rep1eq(i,n) for (int i=1; i<=(int)(n); ++i)
#define rrep(i,n) for (int i=(int)(n)-1; i>=0; --i)
#define rrep1(i,n) for (int i=(int)(n)-1; i>0; --i)
#define rrepeq(i,n) for (int i=(int)(n); i>=0; --i)
#define rrep1eq(i,n) for (int i=(int)(n); i>0; --i)
#define REP(i,a,b) for (int i=(int)(a); i<=(int)(b); ++i)
#define RREP(i,a,b) for (int i=(int)(a); i>=(int)(b); --i)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
template<typename T> using Graph = vector<vector<T>>;
template<typename T> using Spacial = vector<vector<vector<T>>>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<typename T> using greater_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const int MOD = 1e9+7;
const int MOD2 = 998244353;
// const double EPS = 1e-9;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
string interval[2] = {" ", "\n"}; // {" ", "\n"}

template<typename T> struct is_plural : false_type{};
template<typename T1, typename T2> struct is_plural<pair<T1, T2>> : true_type{};
template<typename T> struct is_plural<vector<T>> : true_type{};
template<typename T> struct is_plural<complex<T>> : true_type{};
 
template<typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << " " << p.second; }
template<typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto itr = vec.begin(); itr != vec.end(); ++itr) is >> *itr; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { if (vec.empty()) return os; bool pl = is_plural<T>(); os << vec.front(); for (auto itr = ++vec.begin(); itr != vec.end(); ++itr) os << interval[pl] << *itr; return os; }
 
bool CoutYN(bool a, string y = "Yes", string n = "No") { cout << (a ? y : n) << "\n"; return a; }

template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

long long modpow(int a, long long n, int mod = MOD) { long long ret = 1; do { if (n & 1) ret = ret * a % mod; a = 1LL * a * a % mod; } while (n >>= 1); return ret; }

template<typename T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }
template<typename T> T LCM(T a, T b) { return a / GCD(a, b) * b; }

template<typename T1, typename T2> bool CompareBySecond(pair<T1, T2> a, pair<T1, T2> b) { return a.second != b.second ? a.second < b.second : a.first < b.first; }
template<typename T1, typename T2> bool CompareByInverse(pair<T1, T2> a, pair<T1, T2> b) { return a.first != b.first ? a.first < b.first : a.second > b.second; }


/* -------- <templates end> -------- */


template<uint_fast64_t Modulus = MOD>
struct Modint {
  using u64 = uint_fast64_t;
  u64 a;

  constexpr Modint(const u64 x = 0) noexcept : a(x % Modulus) {}

  constexpr Modint operator+(const Modint rhs) const noexcept {
    return Modint(*this) += rhs;
  }
  constexpr Modint operator-(const Modint rhs) const noexcept {
    return Modint(*this) -= rhs;
  }
  constexpr Modint operator*(const Modint rhs) const noexcept {
    return Modint(*this) *= rhs;
  }
  constexpr Modint operator/(const Modint rhs) const noexcept {
    return Modint(*this) /= rhs;
  }

  constexpr Modint &operator+=(const Modint rhs) noexcept {
    a += rhs.a;
    if (a >= Modulus) a -= Modulus;
    return *this;
  }
  constexpr Modint &operator-=(const Modint rhs) noexcept {
    if (a < rhs.a) a += Modulus;
    a -= rhs.a;
    return *this;
  }
  constexpr Modint &operator*=(const Modint rhs) noexcept {
    a = a * rhs.a % Modulus;
    return *this;
  }
  constexpr Modint &operator/=(Modint rhs) noexcept {
    u64 exp = Modulus - 2;
    while (exp) {
      if (exp & 1) *this *= rhs;
      rhs *= rhs;
      exp >>= 1;
    }
    return *this;
  }

  explicit operator bool() const {
    return a;
  }

  friend ostream &operator<<(ostream &os, const Modint &m) {
    return os << m.a;
  }
};

using mint = Modint<>;

void solve() {
  int n, x; cin >> n >> x;
  vi arr(n); cin >> arr;

  sort(RALL(arr));

  vector<mint> dp(x+1, 0);
  dp[x] = 1;

  rep(i,n) repeq(j,x) if (dp[j]) {
    if (j < arr[i]) {
      dp[j] *= n - i;
      continue;
    }
    dp[j % arr[i]] += dp[j];
    dp[j] *= n - (i+1);
  }

  mint ans = 0;
  repeq(j,x) ans += dp[j] * j;
  cout << ans << endl;
}


/* -------- <programs end> -------- */


signed main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  solve();
  return 0;
}

Python
N,M=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
dp=[[0 for _ in range(M+1)] for _ in range(N+1)]
for i in range(M+1):
    dp[0][i]=i
for i in range(N):
  for j in range(M + 1):
    dp[i + 1][j] = dp[i][j % a[i]] + dp[i][j] * i
    dp[i + 1][j] %= mod
print(dp[-1][M])
Tester's Solution
Java
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

    long MOD = (long)1e9 + 7;

    void run() {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int X = sc.nextInt();

        Integer[] a = new Integer[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        Arrays.sort(a, Comparator.reverseOrder());
        long[][] dp = new long[2][X + 1];
        dp[0][X] = 1;
        int sw = 0;
        for (int i = 0; i < n; i++) {
            sw = 1 - sw;
            Arrays.fill(dp[sw], 0);
            for (int x = 0; x <= X; x++) if (dp[1 - sw][x] > 0) {
                dp[sw][x % a[i]] = (dp[sw][x % a[i]] + dp[1 - sw][x]) % MOD;
                dp[sw][x] = (dp[sw][x] + dp[1 - sw][x] * (n - i - 1)) % MOD;
            }
//            debug(dp[sw]);
        }

        long sum = 0;
        for (int x = 0; x <= X; x++) {
            sum += dp[sw][x] * x;
            sum %= MOD;
        }
        System.out.println(sum);
    }

    void debug(Object...os) {
        System.err.println(Arrays.deepToString(os));
    }

    public static void main(String[] args) {
        new Main().run();
    }
}

Feel free to share your approach.
Suggestions are welcomed, as always had been.