# MODNTEST - EDITORIAL

Contest

Setter: debrc

Tester: mishra_roshan

Editorialist: debrc

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.