Problem:


Score : 600 points

Problem Statement

Snuke has a blackboard and a set S consisting of N integers.
The i-th element in S is S_i.

He wrote an integer X on the blackboard, then performed the following operation N times:

Choose one element from S and remove it.

Let x be the number written on the blackboard now, and y be the integer removed from S. Replace the number on the blackboard with x \bmod {y}.

There are N! possible orders in which the elements are removed from S.
For each of them, find the number that would be written on the blackboard after the N operations, and compute the sum of all those N! numbers modulo 10^{9}+7.

Constraints

All values in input are integers.

1 \leq N \leq 200

1 \leq S_i, X \leq 10^{5}

S_i are pairwise distinct.

Input

Input is given from Standard Input in the following format:

N X
S_1 S_2 \ldots S_{N}

Output

Print the answer.

Sample Input 1

2 19
3 7

Sample Output 1

3

There are two possible orders in which we remove the numbers from S.

If we remove 3 and 7 in this order, the number on the blackboard changes as follows: 19 \rightarrow 1 \rightarrow 1.

If we remove 7 and 3 in this order, the number on the blackboard changes as follows: 19 \rightarrow 5 \rightarrow 2.

The output should be the sum of these: 3.

Sample Input 2

5 82
22 11 6 5 13

Sample Output 2

288

Sample Input 3

10 100000
50000 50001 50002 50003 50004 50005 50006 50007 50008 50009

Sample Output 3

279669259

Be sure to compute the sum modulo 10^{9}+7.



Sample input:
2 19
3 7


Sample output:
3

Submission status: Wrong Answer

Solution code:
import itertools
import math
 
def create_table(s, x, result={}):
    tmp = []
    ll = len(s)
    for i, a in enumerate(s):
        for b in [x for x in s if x != a]:
            t = [a, b]
            c = s.index(b)
            t += [e for j, e in enumerate(s) if j != c and j != i]
            tmp.append(t)
    for a in tmp:
        kk = x
        for b in a:
            kk %= b
        result[(a[0], a[1])] = kk * math.factorial(ll-2)
    return result
 
n, x = map(int, input().split())
s = list(map(int, input().split()))
m = 10 ** 9 + 7
if len(s) >= 2:
    mm = create_table(s, x)
    print(sum([a for a in mm.values()]) % m)
else:
    print((x + (x % s[0])) % m)

Submission status: Wrong Answer

Solution code:
N, X = map(int, input().split())
S = sorted(list(map(int, input().split())))
MIN = S[0]
MOD = 10 ** 9 + 7


# 階乗
factorial = [1]
for i in range(1, N+2):
    factorial.append(factorial[-1] * i % MOD)


append = list.append
stack = [(X, 0)]
ans = 0
while stack:
    X, cnt = stack.pop()
    for s in S:
        if X < s:
            break

        next_X, next_cnt = X % s, cnt + 1

        if next_X < MIN:
            ans += next_X * factorial[N - next_cnt]
            ans %= MOD
        else:
            stack.append((next_X, next_cnt))

print(ans % MOD)

Submission status: Wrong Answer

Solution code:
from math import factorial

N, X = map(int, input().split())
S = list(map(int, input().split()))

MOD = 10**9 + 7


def f(x, s, t):
    if not s:
        return x * factorial(t) % MOD
    res = 0
    for y in s:
        z = x % y
        Z = [v for v in s if v <= z]
        res = (res + f(x % y, Z, len(s) - len(Z) - 1)) % MOD
    return res


T = [s for s in S if s <= X]
ans = f(X, T, len(S) - len(T))
print(ans)

Submission status: Wrong Answer

Solution code:
#a,b,c = [int(i) for i in input().split()]

import sys
input = sys.stdin.readline

MOD = 10**9+7

n,x = [int(i) for i in input().split()]
s = [int(i) for i in input().split()]
#s.sort(reverse=True)

ans = [0]*(x+1)
ans[x] = 1

print(s)
for i, ss in enumerate(s):
    bairitu = n-i-1
#    print(bairitu)
    for j,xx in enumerate(ans):
#        print(j,xx)
        ans[j] = (xx*bairitu)%MOD
        ans[j%ss] = (ans[j%ss]+xx)%MOD

#    print(ans)

res=0
for j,xx in enumerate(ans):
    res += j*xx 
    res = res%MOD

print(res)

Submission status: Wrong Answer

Solution code:
import itertools
import math
n,x = map(int, input().split())
lstS = list(map(int, input().split()))

lstA = list(itertools.permutations(lstS,n))

lstans=[]

for i in range(math.factorial(n)):
    y = x
    for j in range(n):
        y = y % lstA[i][j]
    lstans.append(y)

ans=(sum(lstans))%100000007
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
n, x = map(int, input().split())
nums = list(map(int, input().split()))

ans = 0
for groop in permutations(nums):
    tmp = x
    for num in groop:
        tmp = tmp%num
    ans += tmp
print(round(ans%10**9+7))

Submission status: Wrong Answer

Solution code:
#d
from itertools import permutations

N, X = list(map(int, input().split()))
S = list(map(int, input().split()))

result = 0

for i, perm in enumerate(permutations(S)):
    min_n = float('inf')
    x_temp = X
    for n in perm:
        if n < min_n:
            x_temp = x_temp % n
            min_n = n
    result += x_temp

print(result)

Submission status: Wrong Answer

Solution code:
N, X = map(int, input().split())
S = sorted(list(map(int, input().split())))
MIN = S[0]
MOD = 10 ** 9 + 7


# 階乗
factorial = [1]
for i in range(1, N+2):
    factorial.append(factorial[-1] * i % MOD)


stack = [(X % s, 1) for s in S]
ans = 0
while stack:
    X, cnt = stack.pop()
    add_stack = []
    for s in S:
        if X < MIN:
            ans += X * factorial[N - cnt]
            ans %= MOD
            break
        elif X >= s:
            add_stack.append((X % s, cnt + 1))
        else:
            break

    stack.extend(add_stack)


print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import math

def create_table(s, x, result={}):
    tmp = []
    ll = len(s)
    for i, a in enumerate(s):
        for b in [x for x in s if x != a]:
            t = [a, b]
            c = s.index(b)
            t += [e for j, e in enumerate(s) if j != c and j != i]
            tmp.append(t)
    for a in tmp:
        kk = x
        for b in a:
            kk %= b
        result[(a[0], a[1])] = kk * math.factorial(ll-2)
    return result

n, x = map(int, input().split())
s = list(map(int, input().split()))
m = 10 ** 9 + 7
if len(s) >= 2:
    mm = create_table(s, x)
    print(sum([a for a in mm.values()]) % m)
else:
    print(x % s[0] % m)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,x = LI()
    a = sorted(LI(), reverse=True)
    d = collections.defaultdict(int)
    d[x*256] = 1

    fm = {}
    def f(i):
        if i < 2:
            return 1
        if i in fm:
            return fm[i]
        r = i * f(i-1) % mod
        fm[i] = r
        return r
    fa = []
    for i in range(n+1):
        fa.append(f(i))

    for ai in range(n):
        c = a[ai]
        print(c,len(d))
        e = collections.defaultdict(int)
        for kk,v in d.items():
            k = kk // 256
            i = kk % 256
            v %= mod
            if ai < n-1:
                e[k * 256 + i + 1] += v
            kc = k % c * 256
            e[kc + i] += v
            for j in range(i-1,-1,-1):
                e[kc + j] += v * fa[i] // fa[j]
        d = e

    r = 0
    for kk,v in d.items():
        k = kk // 256
        i = kk % 256
        if i > 0:
            continue
        r += k * v
        r %= mod

    return r


print(main())

Submission status: Wrong Answer

Solution code:
n,x=map(int,input().split())
from math import factorial
s=sorted(list(map(int,input().split())))[::-1]
mods=[]
k=x
for i in s:
 k=k%i
 if k==1:print(factorial(n)%1000000007);exit()
 mods+=[k]
print((factorial(n)+sum(mods)-len(mods))%1000000007)

Submission status: Wrong Answer

Solution code:
import sys
# import bisect
# import math
import itertools
# import numpy as np
# import collections

"""Template"""


class IP:
    """
    入力を取得するクラス
    """

    def __init__(self):
        self.input = sys.stdin.readline

    def I(self):
        """
        1文字の取得に使います
        :return: int
        """
        return int(self.input())

    def S(self):
        """
        1文字の取得(str
        :return: str
        """
        return self.input()

    def IL(self):
        """
        1行を空白で区切りリストにします(int
        :return: リスト
        """
        return list(map(int, self.input().split()))

    def SL(self):
        """
        1行の文字列を空白区切りでリストにします
        :return: リスト
        """
        return list(map(str, self.input().split()))

    def ILS(self, n):
        """
        1列丸々取得します(int
        :param n: 行数
        :return: リスト
        """
        return [int(self.input()) for _ in range(n)]

    def SLS(self, n):
        """
        1列丸々取得します（str
        :param n: 行数
        :return: リスト
        """
        return [self.input() for _ in range(n)]

    def SILS(self, n):
        """
        Some Int LineS
        横に複数、縦にも複数
        :param n: 行数
        :return: list
        """
        return [self.IL() for _ in range(n)]

    def SSLS(self, n):
        """
        Some String LineS
        :param n: 行数
        :return: list
        """
        return [self.SL() for _ in range(n)]


class Idea:
    def __init__(self):
        pass

    def HF(self, p):
        """
        Half enumeration
        半分全列挙です
        pの要素の和の組み合わせを作ります。
        ソート、重複削除行います
        :param p: list : 元となるリスト
        :return: list : 組み合わせられた和のリスト
        """
        return sorted(set(p[i] + p[j] for i in range(len(p)) for j in range(i, len(p))))

    def Bfs2(self, a):
        """
        bit_full_search2
        bit全探索の改良版
        全探索させたら2進数のリストと10進数のリストを返す
        :return: list２つ : １個目 2進数(16桁)  2個目 10進数
        """
        # 参考
        # https://blog.rossywhite.com/2018/08/06/bit-search/
        # https://atcoder.jp/contests/abc105/submissions/4088632
        value = []
        for i in range(1 << len(a)):
            output = []

            for j in range(len(a)):
                if self.bit_o(i, j):
                    """右からj+1番目のiが1かどうか判定"""
                    # output.append(a[j])
                    output.append(a[j])
            value.append([format(i, 'b').zfill(16), sum(output)])

        value.sort(key=lambda x: x[1])
        bin = [value[k][0] for k in range(len(value))]
        val = [value[k][1] for k in range(len(value))]
        return bin, val

    def S(self, s, r=0, m=-1):
        """
        ソート関係行います。色々な設定あります。
        :param s: 元となるリスト
        :param r: reversするかどうか 0=False 1=True
        :param m: （2次元配列）何番目のインデックスのソートなのか
        :return: None
        """
        r = bool(r)
        if m == -1:
            s.sort(reverse=r)
        else:
            s.sort(reverse=r, key=lambda x: x[m])

    def bit_n(self, a, b):
        """
        bit探索で使います。0以上のときにTrue出します
        自然数だからn
        :param a: int
        :param b: int
        :return: bool
        """
        return bool((a >> b & 1) > 0)

    def bit_o(self, a, b):
        """
        bit探索で使います。1のときにTrue出すよ
        oneで1
        :param a: int
        :param b: int
        :return: bool
        """
        return bool(((a >> b) & 1) == 1)

    def ceil(self, x, y):
        """
        Round up
        小数点切り上げ割り算
        :param x: int
        :param y: int
        :return: int
        """
        return -(-x // y)

    def ave(self, a):
        """
        平均を求めます
        :param a: list
        :return: int
        """
        return sum(a) / len(a)

    def gcd(self, x, y):
        if y == 0:
            return x
        else:
            return self.gcd(y, x % y)


"""ここからメインコード"""


def main():
    # 1文字に省略
    r, e, p = range, enumerate, print
    ip = IP()
    id = Idea()
    mod = 10 ^ 9 + 7

    """この下から書いてね"""
    n, x = ip.IL()
    s = ip.IL()
    ans = 0
    o = list(itertools.permutations(s))
    for y in o:
        res = x % y[0]
        for z in y:
            res = res % z
        ans += res

    p(ans % mod)




main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
mod = 10**9+7

def main():
    N, X = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    L = max(A[-1], X)

    dp = [[0]*N for _ in range(L+1)]
    a = A[0]
    for x in range(L+1):
        dp[x][0] = x%a

    dp1 = [[0]*N for _ in range(L+1)] #累積和見たいな
    for n in range(1, N):
        a = A[n]
        for x in range(L+1):
            dp1[x][n] = ((n-1) * dp1[x][n-1] + dp[x][n-1]) % mod
        for x in range(L+1):
            dp[x][n] = dp1[x%a][n]

    ans = 0
    t = 1
    for n in reversed(range(N)):
        ans = (ans + dp[X][n]*t) % mod
        t = t * n % mod

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class mint:
    def __init__(self, x):
        self.__x = x % md

    def __repr__(self):
        return str(self.__x)

    def __neg__(self):
        return mint(-self.__x)

    def __add__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x + other)

    def __sub__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x - other)

    def __rsub__(self, other):
        return mint(other - self.__x)

    def __mul__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * other)

    __radd__ = __add__
    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * pow(other, md - 2, md))

    def __rtruediv__(self, other):
        return mint(other * pow(self.__x, md - 2, md))

    def __pow__(self, power, modulo=None):
        return mint(pow(self.__x, power, md))

md = 10**9+7

def main():
    n,x=MI()
    ss=LI()
    ss.sort()
    dp=[0]*(x+1)
    dp[x]=mint(1)
    for i in range(x,0,-1):
        pre=dp[i]
        if pre==0:continue
        mxj=bisect_right(ss,i)
        for j in range(mxj):
            dp[i%ss[j]]+=pre/mxj

    ev=sum(dp[i]*i for i in range(ss[0]))
    fac=mint(1)
    for i in range(1,n+1):fac*=i
    print(ev*fac)

main()

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-

f = 0


def modulo(x, S):
    for s in S:
        res = x % s
        tmp_S = S[:]
        tmp_S.remove(s)
        if len(tmp_S) > 0:
            modulo(res, tmp_S)
        else:
            global f
            f = f + res
            break


if __name__ == '__main__':
    N, X = map(int, input().split())

    S = list(map(int, input().split()))
    modulo(X, S)

    print(f % (pow(10, 9) + 7))

Submission status: Time Limit Exceeded

Solution code:
def main():
    mod = 10**9+7
    fact = [1, 1]
    for i in range(2, 300):
        fact.append(fact[-1]*i % mod)

    n, x = map(int, input().split())
    s = sorted(list(map(int, input().split())))[::-1]
    memo = [dict() for _ in [0]*(n+1)]
    memo[0][x] = fact[n]
    for i in range(n):
        inv = pow(n-i, mod-2, mod)
        for j, a in memo[i].items():
            m = a*inv % mod
            for k, l in enumerate(s[i:]):
                memo[k+i+1][j % l] = (memo[k+i+1].get(j % l, 0)+m) % mod
    ans = 0
    for i, j in memo[n].items():
        ans = (ans+i*j) % mod
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n,x = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
mod = 10**9+7
rng = 300
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
def inv(a):
  return pow(a,mod-2,mod)
dp = [{} for i in range(n+1)]
dp[0][x] = 1
for i in range(n):
  for j in range(i+1,n+1):
    for k in dp[i].keys():
      num = dp[i][k]
      k %= a[j-1]
      if k in dp[j]:
        dp[j][k] = (dp[j][k]+num*fctr[n-i-1]*inv(fctr[n-j]))%mod
      else:
        dp[j][k] = (num*fctr[n-i-1]*inv(fctr[n-j]))%mod
ans = 0
for i,x in dp[n].items():
  ans = (ans+i*x)%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n,x = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
ls = []
for i in range(n):
  t = x
  for j in range(i+1)[::-1]:
    t %= a[j]
  ls.append(t)
mod = 10**9+7
rng = 300
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
def inv(a):
  return pow(a,mod-2,mod)
dp = [{} for i in range(n+1)]
dp[0][x] = 1
for i in range(n):
  for j in range(i+1,n+1):
    for k in dp[i].keys():
      num = dp[i][k]
      k %= a[j-1]
      if k in dp[j]:
        dp[j][k] = (dp[j][k]+num*fctr[n-i-1]*inv(fctr[n-j]))%mod
      else:
        dp[j][k] = (num*fctr[n-i-1]*inv(fctr[n-j]))%mod
ans = 0
for i,x in dp[n].items():
  ans = (ans+i*x)%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n,x = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
ls = []
for i in range(n):
  t = x
  for j in range(i+1)[::-1]:
    t %= a[j]
  ls.append(t)
mod = 10**9+7
rng = 300
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
def inv(a):
  return pow(a,mod-2,mod)
dp = [defaultdict(int) for i in range(n+1)]
dp[0][x] = 1
for i in range(n):
  for j in range(i+1,n+1):
    for k in dp[i].keys():
      num = dp[i][k]
      k %= a[j-1]
      dp[j][k] = (dp[j][k]+num*fctr[n-i-1]*inv(fctr[n-j]))%mod
ans = 0
for i,x in dp[n].items():
  ans = (ans+i*x)%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
#n = int(input())
#s = input()
n,x = map(int,input().split())
da = list(map(int,input().split()))
m = 100010
mod = 1000000007

dp = [0]*m
da.sort()
da.reverse()
dp[x] = 1
for i in range(n):
    for j in range(m):
        if j >= da[i]:
            dp[j%da[i]] += dp[j]
            dp[j] *= n-i-1
            if dp[j] >= mod: dp[j] %= mod
            if dp[j%da[i]] >= mod: dp[j] %= mod
        else:
            dp[j] *= n-i
            if dp[j] >= mod: dp[j]%=mod
ans = 0
for i in range(m):
    ans += dp[i] * i
    if ans >= mod: ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#n = int(input())
#s = input()
n,x = map(int,input().split())
da = list(map(int,input().split()))
m = 100010
mod = 1000000007

dp = [0 for i in range(m)]
da.sort()
da.reverse()
dp[x] = 1
for i in range(n):
    for j in range(m):
        if j >= da[i]:
            dp[j%da[i]] += dp[j]
            dp[j] *= n-i-1
            if dp[j] >= mod: dp[j] %= mod
            if dp[j%da[i]] >= mod: dp[j] %= mod
        else:
            dp[j] *= n-i
            if dp[j] >= mod: dp[j]%=mod
ans = 0
for i in range(m):
    ans += dp[i] * i
    if ans >= mod: ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# N! 通りの総和は期待値で考えたほうがわかりやすくなることが多そう

import sys
from functools import lru_cache
sys.setrecursionlimit(500000)

def make_modinv_list(n, mod=10**9+7):
    # 0 から n までの mod 逆元のリストを返す O(n)
    modinv = [0, 1]
    for i in range(2, n+1):
        modinv.append(mod - mod//i * modinv[mod%i] % mod)
    return modinv

def main():
    modinv = make_modinv_list(200)

    @lru_cache(maxsize=None)
    def solve(idx, X):
        # 降順ソートした S の idx 個目以降を使ったときの操作後の X の期待値
        if idx == N:
            return X
        # idx 個目を idx 個目以降で最初に使うかで場合分け
        res = 0
        # 最初に使う場合（確率 (1/(N-idx))）
        res += modinv[N-idx] * solve(idx+1, X % S[idx]) % mod
        # 最初に使わない場合（確率 ((N-idx-1)/(N-idx))）
        res += (N-idx-1) * modinv[N-idx] * solve(idx+1, X) % mod
        return res % mod

    mod = 10**9+7
    N, X = map(int, input().split())
    S = sorted(map(int, input().split()), reverse=True)
    ans = solve(0, X)
    for i in range(2, N+1):
        ans = ans * i % mod
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
# N! 通りの総和は期待値で考えたほうがわかりやすくなることが多そう

import sys
from functools import lru_cache
sys.setrecursionlimit(500000)

def make_modinv_list(n, mod=10**9+7):
    # 0 から n までの mod 逆元のリストを返す O(n)
    modinv = [0, 1]
    for i in range(2, n+1):
        modinv.append(mod - mod//i * modinv[mod%i] % mod)
    return modinv

modinv = make_modinv_list(200)

@lru_cache(maxsize=None)
def solve(idx, X):
    # 降順ソートした S の idx 個目以降を使ったときの操作後の X の期待値
    if idx == N:
        return X
    # idx 個目を idx 個目以降で最初に使うかで場合分け
    res = 0
    # 最初に使う場合（確率 (1/(N-idx))）
    res += modinv[N-idx] * solve(idx+1, X % S[idx]) % mod
    # 最初に使わない場合（確率 ((N-idx-1)/(N-idx))）
    res += (N-idx-1) * modinv[N-idx] * solve(idx+1, X) % mod
    return res % mod

mod = 10**9+7
N, X = map(int, input().split())
S = sorted(map(int, input().split()), reverse=True)
ans = solve(0, X)
for i in range(2, N+1):
    ans = ans * i % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, X = list(map(int, input().split()))
S = list(map(int, input().split()))

S_per = list(itertools.permutations(S))

total = 0
for S in S_per:
    x = X
    for i in range(len(S)):
        x = x % S[i]
    total += x
    
total = total % (10**9 + 7)
print(total)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)

MOD = 10**9 + 7

N, X = map(int, input().split())
Ss = list(map(int, input().split()))

Ss.sort(reverse=True)

def dfs(i, xNow):
    if (i, xNow) in memo:
        return memo[(i, xNow)]
    if i == N-1:
        ans = xNow % Ss[i]
    else:
        ans = dfs(i+1, xNow % Ss[i])
        ans += dfs(i+1, xNow) * (N-i-1)
    ans %= MOD
    memo[(i, xNow)] = ans
    return ans

memo = {}
dfs(0, X)

print(memo[(0, X)])

Submission status: Time Limit Exceeded

Solution code:
N,X=map(int, input().split())
S=[int(c) for c in input().split()]
S.sort()
dp=dict()
def find(x, n):
    k = (x, n)
    if k in dp:
        return dp[k]
    sn=S[n]
    if n == 0:
        return x % sn
    r = n*find(x, n-1) + find(x%sn, n-1)
    dp[k] = r
    return r
print(find(X, N-1)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
N,X = map(int,input().split())
S = list(map(int,input().split()))
S.sort()
mod = 10**9+7

dp = [[0]*(N+1) for i in range(X+1)]
for x in range(X+1):
    for n in range(N+1):
        if n == 0:
            dp[x][n] = x
        else:
            dp[x][n] = (dp[x%S[n-1]][n-1] + (n-1)*dp[x][n-1])%mod

print(dp[X][N])

Submission status: Time Limit Exceeded

Solution code:
N,X = map(int,input().split())
S = list(map(int,input().split()))
S.sort()
mod = 10**9+7

def E(x,n):
    if n==0:
        return x
    else:
        return (E(x%S[n-1],n-1)+(n-1)*E(x,n-1))%mod

print(E(X,N))

Submission status: Time Limit Exceeded

Solution code:
N,X =  map(int, input().split())
s = list(map(int, input().split()))

import math
import copy

modu = 1000000007

factorial_table = [0] * 201
for i in range(201):
	factorial_table[i] = math.factorial(i) % modu

def get_residue_sum(a, li, length):
	if li == []:
		return a
	if a < min(li):
		# 残り全部a
		return a * factorial_table[length]
	elif length == 1:
		return a % li[0]
	else:
		new_li = [x for x in li if x <= a]
		new_len = len(new_li)

		summ = 0
		for idx in range(new_len):
#			li から iを削除して
			li2 = copy.deepcopy(new_li)
			q = li2.pop(idx)
			summ += get_residue_sum(a%q, li2, new_len-1)

		for i in range(new_len+1, length+1):
			summ *= i
		return (summ % modu)

ans = get_residue_sum(X, s, N) % modu
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD=10**9+7
N,X=map(int,input().split())
S=list(map(int,input().split()))
S.sort()
dp=[{} for i in range(N)]
# 初回
for i in range(N):
    y=S[i]
    dp[i][X%y]=1
# 回数ごと
for n in range(1,N):
    dp_n=[{} for i in range(N)]
    # 前回までの最小値ごと
    for i in range(N-n+1):
        # 前回までの最小値より小さい値の選択
        for iy in range(i):
            y=S[iy]
            for x in dp[i]:
                if x%y not in dp_n[iy]:
                    dp_n[iy][x%y]=0
                dp_n[iy][x%y]+=dp[i][x]
                dp_n[iy][x%y]%=MOD
        # 前回までの最小値以上の選択
        y=S[i]
        for x in dp[i]:
            if x%y not in dp_n[i]:
                dp_n[i][x%y]=0
            dp_n[i][x%y]+=dp[i][x]*(N-n-i)
            dp_n[i][x%y]%=MOD
    dp=dp_n
ans=0
for x in dp[0]:
    ans+=dp[0][x]*x
    ans%=MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, X = map(int, input().split())
S = input().split()


MOD = 1000000007
numbers = np.array(S).astype(np.int64)
numbers = np.sort(numbers)


#dp = np.zeros((N+1, X+1), dtype=int)
dp = np.arange(X+1)
dp_n = []
i = 0
for n  in numbers:
    dp_n = np.zeros((X+1), dtype=np.int64)
    dp_n += [dp[x % n] for x in range(X+1)]
    dp_n = dp_n % MOD
    dp_n += dp * i % MOD
    dp_n = dp_n % MOD
    dp = dp_n
    i += 1

print(int(dp_n[X]) % MOD)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, X = map(int, input().split())
S = input().split()

MOD = 1000000007
numbers = np.array(S).astype(np.int64)
numbers.sort()


dp = np.zeros((N+1, X+1), dtype=int)
dp = np.arange(X+1)
dp_n = []
i = 0
for n  in numbers:
    dp_n = np.zeros((X+1), dtype=np.int64)
    dp_n += [dp[x % n] for x in range(X+1)]
    dp_n = dp_n % MOD
    dp_n += dp * i % MOD
    dp_n = dp_n % MOD
    dp = dp_n
    i += 1

print(int(dp_n[X]) % MOD)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, X = map(int, input().split())
S = list(map(int, input().split()))


MOD = 1000000007
numbers = S[:]
numbers.sort()


dp = np.zeros((N+1, X+1), dtype=int)
dp = np.arange(X+1)
dp_n = []
i = 0
for n  in numbers:
    dp_n = np.zeros((X+1), dtype=np.int64)
    dp_n += [dp[x % n] for x in range(X+1)]
    dp_n = dp_n % MOD
    dp_n += dp * i % MOD
    dp_n = dp_n % MOD
    dp = dp_n
    i += 1

print(int(dp_n[X]) % MOD)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, X = map(int, input().split())
S = list(map(int, input().split()))


MOD = 1000000007
numbers = S[:]
numbers.sort()


dp = np.zeros((N+1, X+1), dtype=int)
dp = np.arange(X+1)
dp_n = []
for i, n  in enumerate(numbers):
    dp_n = np.zeros((X+1), dtype=np.int64)
    dp_n += [dp[x % n] for x in range(X+1)]
    dp_n = dp_n % MOD
    dp_n += dp * i % MOD
    dp_n = dp_n % MOD
    dp = dp_n

print(int(dp_n[X] % MOD))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, X = map(int, input().split())
S = list(map(int, input().split()))

MOD = 1000000007
numbers = S[:]
numbers.sort()


dp = np.zeros((N+1, X+1), dtype=int)
#dp[0] = [x for x in range(X+1)]
dp[0] = np.arange(X+1)

for i, n  in enumerate(numbers):
    for x in range(X+1):
        dp[i+1][x] += dp[i][x % n]
    dp[i+1] += dp[i] * i 

print(int(dp[N][X] % MOD))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, X = map(int, input().split())
S = list(map(int, input().split()))

MOD = 1000000007
numbers = S[:]
numbers.sort()


dp = np.zeros((N+1, X+1), dtype=np.int64)
dp[0] = [x for x in range(X+1)]


for i, n  in enumerate(numbers):
    for x in range(X+1):
        dp[i+1][x] += dp[i][x % n]
        dp[i+1][x] += dp[i][x] * i 

print(int(dp[N][X] % MOD))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, X = map(int, input().split())
S = list(map(int, input().split()))


MOD = 1000000007
numbers = S[:]
numbers.sort()


dp = np.zeros((N+1, X+1))
dp[0] = [x for x in range(X+1)]


for i, n  in enumerate(numbers):
    for x in range(X+1):
        dp[i+1][x] += dp[i][x % n]
        dp[i+1][x] += dp[i][x] * i 

print(int(dp[N][X] % MOD))

Submission status: Time Limit Exceeded

Solution code:
N, X = map(int, input().split())
S = list(map(int, input().split()))

MOD = 1000000007
numbers = S[:]
numbers.sort()


#dp = [[0] * (X+1) for _ in range(N+1)]
dp = [None]
dp[0] = [x for x in range(X+1)]


for i, n  in enumerate(numbers):
    dp.append([0] * (X+1))
    for x in range(X+1):

        dp[i+1][x] += dp[i][x % n]
        dp[i+1][x] += dp[i][x] * i 

print(dp[N][X] % MOD)

Submission status: Time Limit Exceeded

Solution code:
N, X = map(int, input().split())
S = list(map(int, input().split()))

MOD = 1000000007
numbers = S[:]
numbers.sort()


#dp = [[0] * (X+1) for _ in range(N+1)]
dp = [None]
dp[0] = [x for x in range(X+1)]


for i, n  in enumerate(numbers):
    dp.append([])
    for x in range(X+1):
        dp[i+1].append(0)
        dp[i+1][x] += dp[i][x % n]
        #dp[i+1][x] = dp[i+1][x] % MOD
        dp[i+1][x] += dp[i][x] * i % MOD
        #dp[i+1][x] = dp[i+1][x] % MOD

print(dp[N][X] % MOD)

Submission status: Time Limit Exceeded

Solution code:
N, X = map(int, input().split())
S = list(map(int, input().split()))


MOD = 1000000007
numbers = S[:]
numbers.sort()
#dp = [[0 for _ in range(X+1)] for _ in range(N+1)]

dp = [[0] * (X+1) for _ in range(N+1)]
#dp[0] = [x for x in range(X+1)]
#from collections import defaultdict
#dp = [defaultdict(int) for _ in range(N+1)]
dp[0] = [x for x in range(X+1)]

import array 
dp = [array.array('Q', l) for l in dp]

for i, n  in enumerate(numbers):
    for x in range(X+1):
        dp[i+1][x] += dp[i][x % n]
        dp[i+1][x] = dp[i+1][x] % MOD
        dp[i+1][x] += dp[i][x] * i % MOD
        dp[i+1][x] = dp[i+1][x] % MOD

print(dp[N][X] % MOD)

Submission status: Time Limit Exceeded

Solution code:
N, X = map(int, input().split())
S = list(map(int, input().split()))

MOD = 1000000007
numbers = S[:]
numbers.sort()
#dp = [[0 for _ in range(X+1)] for _ in range(N+1)]
dp = [[0] * (X+1) for _ in range(N+1)]

#dp[0] = [x for x in range(X+1)]
#from collections import defaultdict
#dp = [defaultdict(int) for _ in range(N+1)]
dp[0] = [x for x in range(X+1)]

for i, n  in enumerate(numbers):
    for x in range(X+1):
        dp[i+1][x] += dp[i][x % n]
        dp[i+1][x] += dp[i][x] * i #% MOD

print(dp[N][X] % MOD)

Submission status: Time Limit Exceeded

Solution code:
N, X = map(int, input().split())
S = list(map(int, input().split()))

MOD = 1000000007
numbers = S[:]
numbers.sort()
#dp = [[0 for _ in range(X+1)] for _ in range(N+1)]
#dp = [[0] * (X+1) for _ in range(N+1)]

#dp[0] = [x for x in range(X+1)]
from collections import defaultdict
dp = [defaultdict(int) for _ in range(N+1)]
dp[0] = [x for x in range(X+1)]

for i, n  in enumerate(numbers):
    for x in range(X+1):
        dp[i+1][x] += dp[i][x % n]
        #dp[i+1][x] = dp[i+1][x] % MOD
        
        dp[i+1][x] += dp[i][x] * i #% MOD
        #dp[i+1][x] = dp[i+1][x] % MOD

print(dp[N][X] % MOD)