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: Accepted

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)
 
YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
input=lambda: sys.stdin.readline().rstrip()

class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=0):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.size=len(ls)+1
                self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def __str__(self):
        return  str(self.edges)
 
    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v
 
    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.size
        self.ETout=[-1]*self.size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]
 
class SparseTable: # O(N log N) for init, O(1) for query(l,r)
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1
 
        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    # return func of [l,r)
    def query(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))])
    
    # return index of which val[i] = func of v among [l,r)
    def query_id(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][max(0,r-(1<<N))]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))]):
            b=a
        return b
    
    def __str__(self):
        return str(self.table[0])
 
    def print(self):
        for i in self.table:
            print(*i)

show_flg=False
show_flg=True
ans=0


n,x=LI()
s=LI()
s.sort(reverse=True)
X=x

dp=[[0]*(X+1) for i in range(n+1)]
dp[0][X]=1

for i in range(n):
    for j in range(X+1):
        dp[i+1][j%s[i]]+=dp[i][j]%mo
        dp[i+1][j]+=dp[i][j]*(n-i-1)%mo

ans=sum([(i)*dp[n][i] for i in range(X+1)])
print(ans%mo)

Submission status: Accepted

Solution code:
N, X = map(int, input().split())
S = list(map(int, input().split()))
S.sort(reverse=True)
dp = [[0]*(X+1) for _ in range(N+1)]
dp[0][X] = 1
MOD = 10**9+7

for i in range(N):
    for j in range(X+1):
        dp[i+1][j%S[i]] += dp[i][j]
        dp[i+1][j%S[i]] %= MOD
        dp[i+1][j] += (N-i-1)*dp[i][j]
        dp[i+1][j] %= MOD

ans = 0

for i in range(X+1):
    ans += dp[N][i]*i
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
N,X=map(int,input().split())
S=list(map(int,input().split()))
S.sort()
mod=10**9+7
dp=[[0 for i in range(10**5+1)] for j in range(N)]

for i in range(10**5+1):
    dp[0][i]=i%S[0]

for i in range(1,N):
    for j in range(10**5+1):
        dp[i][j]=(i*dp[i-1][j]+dp[i-1][j%S[i]])%mod

print(dp[N-1][X])

Submission status: Accepted

Solution code:
N,X=map(int,input().split())
S=list(map(int,input().split()))
pr=10**9+7
b={X:1}
S.sort(reverse=1)
def ir(k,v):
    global d
    if k in d:
        d[k]=(d[k]+v)%pr
    else:
        d[k]=v
for i in range(N):
    t=S[i]
    n=N-i-1
    d={}
    for k,v in b.items():
        ir(k%t,v)
        ir(k,v*n)
    b=d
a=0
for k,v in b.items():
    a=(a+k*v)%pr
print(a)

Submission status: Accepted

Solution code:
n, x = map(int, input().split())
s = list(map(int, input().split()))
MOD = 10 ** 9 + 7

s = sorted(s, reverse=True)
max_ = max(s[0], x)
dp = [[0] * (max_ + 1) for i in range(n + 1)]
dp[0][x] = 1

for i in range(n):
    for val in range(max_ + 1):
        dp[i + 1][val % s[i]] += dp[i][val]
        dp[i + 1][val % s[i]] %= MOD
        dp[i + 1][val] += dp[i][val] * (n - i - 1)
        dp[i + 1][val] %= MOD

ans = 0
for i, num in enumerate(dp[-1]):
    ans += num * i
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,x = LI()
    s = LI()
    s.sort()
    dp = [[0]*(n+1) for i in range(x+1)]
    for i in range(n):
        si = s[i]
        ni = i+1
        for j in range(x+1):
            dp[j][0] = j
            nd = (dp[j%si][i]+i*dp[j][i])%mod
            dp[j][ni] += nd
    print(dp[x][n]%mod)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, X = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
a.sort()
dp = [[0] * (X + 1) for _ in range(N + 1)]
for j in range(X + 1): dp[0][j] = j
for i in range(N):
  for j in range(X + 1):
    dp[i + 1][j] = dp[i][j % a[i]] + dp[i][j] * i
    dp[i + 1][j] %= mod
print(dp[-1][X])

Submission status: Accepted

Solution code:
n,x=map(int,input().split());s,f,M=sorted(list(map(int,input().split())))[::-1],[1,1],10**9+7
for i in range(2,n):f+=[f[-1]*i%M]
D={x:f[n-1]}
for i, k in enumerate(s):
 m,inv=dict(),pow(n-i-1,M-2,M)
 for j,a in D.items():m[j%k]=(m.get(j%k,0)+a)
 for j,a in m.items():D[j]=(D.get(j,0)+a*inv)%M
print(sum([i*j for i, j in m.items()])%M)

Submission status: Accepted

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]
    next_dict = {x: fact[n-1]}
    for i in range(n):
        memo = dict()
        inv = pow(n-i-1, mod-2, mod)
        ss = s[i]
        for j, a in next_dict.items():
            memo[j % ss] = (memo.get(j % ss, 0)+a) % mod
        for j, a in memo.items():
            next_dict[j] = (next_dict.get(j, 0)+a*inv) % mod
    ans = 0
    for i, j in memo.items():
        ans = (ans+i*j) % mod
    print(ans)


main()

Submission status: Accepted

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
dp = [defaultdict(int) for i in range(n+1)]
dp[0][x] = 1
for i in range(1,n+1):
  for j in dp[i-1].keys():
    k = j%a[i-1]
    dp[i][j] = (dp[i][j]+dp[i-1][j]*(n-i))%mod
    dp[i][k] = (dp[i][k]+dp[i-1][j])%mod
ans = 0
for i,x in dp[n].items():
  ans = (ans+i*x)%mod
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n, x = LI()
S = sorted(LI())
dp = [[0] * (x + 1) for _ in range(n + 1)]
for i in range(x + 1):
    dp[0][i] = i



for j in range(n):
    for k in range(x + 1):
        dp[j + 1][k] = (dp[j][k % S[j]] + dp[j][k] * j) % mod


print(dp[n][x])

Submission status: Accepted

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/exawizards2019/tasks/exawizards2019_d

結局はS中で最小の物以下になる
また、それ以下になったらもう変化しない

通り数を数えなくてはダメ
→0以上min(S)未満の整数kに関して、最後にkになっているのは何通りあるかを数える？

大きい方からdp

具体的には、小さい方で割ったのちに大きい方で割るのは意味がないので大きい方から見ていく
dp[i][n] = 大きい方からi番目までの中で黒板に書かれてる数字がnとなる順序数

推移は、普通に割ったあまりのとこに推移させる & 自分が最初に来た後　
O(max(X,S)*N)

→解けて無いなぁ(途中に来た場合をどうやって数え上げるんですか…)
計算量にNが2回かかってしまう…

影響のあるやつだけ考える？
大きい方から、変化のあるやつだけ取っていく。min(S)以下になったら終了。変化のない奴の位置の組み合わせは…？

N枚のカードをN個あるスロットルに入れ、右側から黒板に向けて射出していくことを考える
dp[i][j] = i枚目までスロットルに入れた時、今射出して黒板の数字がjになる置き方の組み合わせ数
とすれば、Sより大きいjに関しては割ればよいし、そうでなければそれ以降の好きなところにおいてよいので…？
→いやなんか違うな

=========解説を見た=========
https://drken1215.hatenablog.com/entry/2019/04/01/201600
dp[i][x]=
スタート時点での整数がxであるときに、最初のi個についての順列すべてを考えたときに得られる値の総和

うーん総和を直接dpしちゃうのかぁ…
小さい方から見た時に、最初以外に入れても変化しないので
dp[i+1][x] = i * dp[i][x] + dp[i][x % s[i+1]]

→小さい方から見ればよかったかぁ…あと、xをすべてdpに乗せて調べ上げるという発想はなかった…
（無意識のうちに無理だろと思ってしまっていた）


"""
mod = 10**9+7
N,X = map(int,input().split())

S = list(map(int,input().split()))
S.sort()

dp = [[ i for i in range(X+1) ] for j in range(N+1)]

for i in range(N):

    for x in range(X+1):

        dp[i+1][x] = ((i) * dp[i][x] + dp[i][x % S[i]]) % mod


print (dp[N][X])

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    N, x = map(int, input().split())
    S = list(map(int, input().split()))
    S.sort(reverse=True)
    mod = 1000000007

    ans = [0] * (10**5+1)
    ans[x] = 1
    for i, s in enumerate(S):
        for j in range(10**5+1):
            aj = ans[j]
            ans[j%s] = (ans[j%s] + aj)%mod
            ans[j] = (ans[j] + aj * (N-i-2))%mod
    ret = 0
    for k, a in enumerate(ans):
        ret = (ret + (a*k)%mod)%mod
    print(ret)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

MOD = 10**9+7
n, x = map(int, input().split())
S = sorted(map(int, input().split()), reverse=True)
dp = [defaultdict(int) for _ in range(n+1)]
dp[0][x] = 1
for i in range(n):
  now = S[i]
  for j in dp[i]:
    dp[i+1][j%now] += dp[i][j]
    dp[i+1][j] += dp[i][j] * (n-1-i)
    dp[i+1][j%now] %= MOD
    dp[i+1][j] %= MOD
ans = 0
for k, v in dp[n].items():
  ans += k*v
  ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from math import factorial
from collections import defaultdict

MOD = 10**9+7
n, x = map(int, input().split())
S = sorted(map(int, input().split()), reverse=True)
dp = [defaultdict(int) for _ in range(n+1)]
dp[0][x] = 1
for i in range(n):
  now = S[i]
  p = pow(n-i, MOD-2, MOD)
  q = p*(n-1-i)%MOD
  for j in dp[i]:
    dp[i+1][j%now] += dp[i][j] * p
    dp[i+1][j] += dp[i][j] * q
    dp[i+1][j%now] %= MOD
    dp[i+1][j] %= MOD
ans = 0
for k, v in dp[n].items():
  ans += k*v
  ans %= MOD
ans *= (factorial(n) % MOD)
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
N, X = map(int, input().split())
S = [int(i) for i in input().split()]

mod = 10 ** 9 + 7

S.sort(reverse=True)

dp = [0] * (X + 1)
dp[X] = 1

for i in range(N) :
  ndp = [0] * (X + 1)
  for j in range(X + 1) :
    ndp[j%S[i]] += dp[j]
    ndp[j%S[i]] %= mod
    if i != N - 1 :
      ndp[j] += dp[j] * (N - 1 - i)
      ndp[j] %= mod
  dp = ndp

ret = 0
for i in range(X + 1) :
  ret += i * dp[i] % mod
  ret %= mod

print(ret)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


# 挿入dp
def solve():
    n,x = LI()
    s = LI()
    s.sort()
    dp = [[0]*(x+1) for i in range(n+1)] # dp[i][j] := スタート時点の値がjの時に最初のi個の順列すべてを試し、えられる総和
    for j in range(x+1):
        dp[0][j] = j # dpの定義より明らか
        for i in range(n):
            si = s[i]
            ni = i+1
            nd = dp[i][j%si] # 先頭にsiを挿入 (スタートの値がj%siとなる)
            nd += i*dp[i][j] # 先頭以外にsiを挿入 (スタートの値も間の値も変わらない)
            dp[ni][j] += nd
            if dp[ni][j] >= mod:
                dp[ni][j] %= mod
    print(dp[n][x])
    return

# 空間の節約
def solve_1():
    n,x = LI()
    s = LI()
    s.sort()
    #dp = [[0]*(x+1) for i in range(n+1)] # dp[i][j] := スタート時点の値がjの時に最初のi個の順列すべてを試し、えられる総和
    dp = [j for j in range(x+1)]
    for i in range(n):
        si = s[i]
        ndp = [0]*(x+1)
        for j in range(x+1):
            nd = dp[j%si] # 先頭にsiを挿入 (スタートの値がj%siとなる)
            nd += i*dp[j] # 先頭以外にsiを挿入 (スタートの値も間の値も変わらない)
            ndp[j] += nd
            if ndp[j] >= mod:
                ndp[j] %= mod
        dp = [j for j in ndp]
    print(dp[x])
    return

#Solve
if __name__ == "__main__":
    solve_1()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


# 挿入dp
def solve():
    n,x = LI()
    s = LI()
    s.sort()
    dp = [[0]*(x+1) for i in range(n+1)] # dp[i][j] := スタート時点の値がjの時に最初のi個の順列すべてを試し、えられる総和
    for j in range(x+1):
        dp[0][j] = j # dpの定義より明らか
        for i in range(n):
            si = s[i]
            ni = i+1
            nd = dp[i][j%si] # 先頭にsiを挿入 (スタートの値がj%siとなる)
            nd += i*dp[i][j] # 先頭以外にsiを挿入 (スタートの値も間の値も変わらない)
            dp[ni][j] += nd
            if dp[ni][j] >= mod:
                dp[ni][j] %= mod
    print(dp[n][x])
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def solve():
  n,x = (int(i) for i in input().split())
  s = sorted(list(int(i) for i in input().split()))
  dp = [[0]*(x+1) for _ in range(n+2)]
  for i in range(x):
    dp[0][i] = i
  mod = 10**9+7
  for i in range(n):
    for j in range(x+1):
      dp[i+1][j] += dp[i][j%s[i]]
      dp[i+1][j] %= mod
      dp[i+1][j] += dp[i][j]*i
      dp[i+1][j] %= mod
  print(dp[n][x])
  
solve()

Submission status: Accepted

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

n, k = [int(item) for item in input().split()]
s = [int(item) for item in input().split()]
s.sort(reverse=True)
MAX_VAL = max(max(s), k)

dp = [[0] * (MAX_VAL + 1) for _ in range(n + 1)]
dp[0][k] = 1
for i, item in enumerate(s):
    for j in range(MAX_VAL + 1):
        if dp[i][j] == 0:
            continue
        # Apply item
        dp[i+1][j % item] += dp[i][j]
        dp[i+1][j % item] %= MOD
        # Put item afterwards
        dp[i+1][j] += dp[i][j] * (n - 1 - i)
        dp[i+1][j] %= MOD

ans = 0
for i, item in enumerate(dp[n]):
    ans += i * item
    ans %= MOD
print(ans)

Submission status: Accepted

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

S = sorted(list(map(int, input().split())))
S_max = 10**5
dp = [[0]*(S_max+1) for _ in range(N+1)]

for x in range(S_max+1):
    dp[0][x] = x
for i in range(1, N+1):
    for x in range(S_max+1):
        dp[i][x] = (dp[i-1][x]*(i-1)+dp[i-1][x%S[i-1]])%mod
print(dp[N][X]%mod)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
N, X = map(int, readline().split())
S = list(map(int, readline().split()))
S.sort(reverse = True)
maxS = 10**5 + 1
mod = 10**9+7
dp = [0]*maxS
dp[X] += 1
for i in range(N):
    s = S[i]
    dp2 = [d*(N-1-i)%mod for d in dp]
    for j in range(1, maxS):
        dp2[j%s] = (dp2[j%s] + dp[j])%mod
    dp = dp2[:]
ans = 0
for i in range(maxS):
    ans = (ans + i*dp[i])%mod
print(ans)

Submission status: Accepted

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 memo[i][xNow] != -1:
        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 = [[-1]*(X+1) for _ in range(N+1)]
dfs(0, X)

print(memo[0][X])

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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

Ss.sort(reverse=True)
minS = Ss[-1]

D = {X: 1}
for i, S in enumerate(Ss[:-1]):
    D2 = {}
    for x, num in D.items():
        D2[x] = (D2.get(x, 0) + num*(N-1-i)) % MOD
        D2[x%S] = (D2.get(x%S, 0) + num) % MOD
    D = D2

ans = 0
for x, num in D.items():
    ans += (x%minS) * num % MOD
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np
MOD = 10 ** 9 + 7

N,X = map(int,input().split())
S = [int(x) for x in input().split()]
S.sort()

# xから始めて集合S0, ..., Sk まででどうなるか

dp = np.arange(X+1, dtype=np.int64)

for i,s in enumerate(S):
    prev = dp
    dp = i * prev # sをあとまわしで使う場合
    dp += prev[np.arange(X+1) % s] # 初手sを使う
    dp %= MOD

answer = dp[-1]
print(answer)

Submission status: Accepted

Solution code:
import math
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N, X = list(map(int, sys.stdin.readline().split()))
S = list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7


def mod_invs(max, mod):
    """
    逆元のリスト 0 から max まで
    :param max:
    :param mod:
    :return:
    """
    invs = [1] * (max + 1)
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


S.sort()

invs = mod_invs(N, MOD)
dp = np.arange(X + 1) % S[0]
for i in range(1, N):
    dp += dp[np.arange(X + 1) % S[i]] * invs[i]
    dp %= MOD
print(int(dp[X] * math.factorial(N) % MOD * invs[N] % MOD))

Submission status: Accepted

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

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

print(dp[X][N])

Submission status: Accepted

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

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

print(dp[X][N])

Submission status: Accepted

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

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


dp = {X: 1}

for i, n in enumerate(numbers):
    tmp_dp = {}
    for k, v in dp.items():
        if k < n:
            tmp_dp[k] = (tmp_dp.get(k,0)+v*(N-i))
        else:
            tmp_dp[k]=(tmp_dp.get(k,0)+v*(N-i-1)) 
            tmp_dp[k%n]=(tmp_dp.get(k%n,0)+v) 
    dp = tmp_dp.copy()
        
ans = 0
for k, v in dp.items():
    ans += k *  v

print(ans % MOD)

Submission status: Accepted

Solution code:
import math

def cul(i,x):
    if tmp[i][x]==-1:
        tmp[i][x]=( cul(i+1,x)*(N-1-i) + cul(i+1,x%a[i]) )%MOD
    return tmp[i][x]

MOD=10**9+7
N,x=map(int,input().split())

a=list(map(int,input().split()))
a.sort(reverse=True)
tmp= [[-1 for j in range(x+1)] for i in range(N)] + [[j for j in range(x+1)]]

print(cul(0,x))

Submission status: Accepted

Solution code:
N, X = map(int, input().split())
S = list(map(int, input().split()))
MOD = 10 ** 9 + 7
dp = [[0] * (X + 1) for i in range(N + 1)]
for i in range(X + 1):
    dp[0][i] = i

S = sorted(S)
for i in range(N):
    for j in range(X + 1):
        dp[i + 1][j] += dp[i][j % S[i]] + dp[i][j] * i
        dp[i + 1][j] %= MOD

print(dp[N][X])

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import defaultdict

MOD = 10**9+7

n,x = li()
s = list(li())
s.sort(reverse=True)

dd = defaultdict(int)

dd[x] = 1

for i in range(n):
    nexdd = defaultdict(int)
    
    for k, v in dd.items():
        nexdd[k] += dd[k] * (n-i-1)
        nexdd[k] %= MOD
        
        nexdd[k%s[i]] += dd[k]
        nexdd[k%s[i]] %= MOD
        
    dd = nexdd
    
ans = 0
for k,v in dd.items():
    ans += k*v
    ans %= MOD
    
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(20000000)
input = sys.stdin.readline
n,x = map(int,input().split())
s = list(map(int,input().split()))
mod = 10**9 + 7
s.sort()
s = s[::-1]
c = max(max(s),x)
dp = [[0]*(c+1) for i in range(n+1)]
dp[0][x] = 1
for i in range(n):
    for j in range(c+1):
        dp[i+1][j%s[i]] += dp[i][j]
        dp[i+1][j%s[i]] %= mod
        dp[i+1][j] += dp[i][j]*(n-i-1)
        dp[i+1][j] %= mod
ans = 0
for i in range(c+1):
        ans += dp[n][i]*i
        ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
def input():
	return sys.stdin.readline()[:-1]

MOD = 1e9+7
n, x = map(int, input().split())
s = list(map(int, input().split()))
s.sort(reverse=True)
dp = defaultdict(int)
dp[x] = 1
for i in range(n):
	ss = s[i]
	dpp = defaultdict(int)
	for key, value in dp.items():
		dpp[key] += (n-1-i) * value
		dpp[key%ss] += value
	for key in dpp.keys():
		dpp[key] %= MOD
	dp = dpp
ans = 0
for key, value in dp.items():
	ans += value * key
	ans %= MOD
print(int(ans))

Submission status: Accepted

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

MOD = 10**9+7
memo = [{} for i in range(N)]
S.sort(reverse=True)

def ddp(cur_N, cur_x):
    if cur_N == N:
        return cur_x
    if cur_x in memo[cur_N]:
        return memo[cur_N][cur_x]
    ret = ddp(cur_N+1, cur_x % S[cur_N]) + ddp(cur_N+1, cur_x)*(N-cur_N-1)
    ret = ret % MOD
    memo[cur_N][cur_x] = ret
    return ret
print(ddp(0, X))

Submission status: Accepted

Solution code:
from collections import defaultdict as dd

N, X = [int(i) for i in input().split()]
sList = [int(i) for i in input().split()]
sList.sort(reverse=True)
mod = 10 ** 9 + 7

dp = dd(int)
dp[X] = 1
for i, s in enumerate(sList):
    new_dp = dd(int)
    for x in dp:
        new_dp[x] += dp[x] * (N - i - 1)
        new_dp[x] %= mod
        new_dp[x % s] += dp[x]
        new_dp[x % s] %= mod
    dp = new_dp

ans = 0
for x in dp:
    ans += x * dp[x]
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

from collections import defaultdict


n, X = map(int, input().split())
s = list(map(int, input().split()))
s = sorted(s, reverse=True)

mod = 10 ** 9 + 7

dp = defaultdict(int)
dp[X] = 1

for i in range(n):
    new_dp = defaultdict(int)

    for x in dp:
        mod_x = x % s[i]
        new_dp[x] += dp[x] * (n - i - 1)
        new_dp[mod_x] += dp[x]

    dp = new_dp

total = 0
for x in dp:
    total += dp[x] * x

total %= mod

print(total)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def solve(N: int, X: int, S: "List[int]"):
    fact = [0] * (N + 1)
    fact[1] = 1
    for i in range(2, N + 1):
        fact[i] = fact[i - 1] * i

    memo = [[-1] * (X + 1) for _ in range(N + 1)]
    S.sort(reverse=True)
    def rec(idx, x, d=0):
        #suf = ''.join(['  ' for _ in range(d)])
        #print(suf, idx, x)
        if memo[idx][x] >= 0:
            return memo[idx][x]
        if idx == N - 1:
            memo[idx][x] = x % S[idx]
            return memo[idx][x]
        ret = 0

        ret += rec(idx + 1, x, d + 1) * (N - idx - 1)
        ret += rec(idx + 1, x % S[idx], d + 1)

        #for i in range(idx + 1, N):
        #    ret += rec(i, x, d + 1) * (N - idx - 1)
        #    ret += rec(i, x % S[idx], d + 1)
        #print(suf, idx, x, ' =>', ret)
        memo[idx][x] = ret
        return ret

    ret = rec(0, X)
    print(ret % MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    S = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, X, S)

if __name__ == '__main__':
    main()