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:
n, x = [int(i) for i in input().split()]
S = [int(i) for i in input().split()]
DP = [[0] * (x + 1) for i in range(n + 1)]
DP[0][x] = 1
p = 10 ** 9 + 7
S.sort(reverse=True)

for i in range(n):
    for j in range(x + 1):
        DP[i][j] %= p
        if i != n - 1:
            DP[i + 1][j] += DP[i][j] * (n - i - 1)
        DP[i + 1][j % S[i]] += DP[i][j]

print(sum(i * d % p for i, d in enumerate(DP[n])) % p)

Submission status: Accepted

Solution code:
from collections import defaultdict


def prepare(n, MOD):
    f = 1
    factorials = [1]
    for i in range(1, n + 1):
        f = f * i % MOD
        factorials.append(f)
    return factorials


n, x = map(int, input().split())
sss = list(map(int, input().split()))
sss.sort(reverse=True)
ms = sss.pop()
MOD = 10 ** 9 + 7
factorials = prepare(n, MOD)
dp = {x: 1}
ans = 0
for i, s in enumerate(sss):
    ndp = defaultdict(lambda: 0)
    k = n - i
    for y, c in dp.items():
        if y < s:
            ndp[y] = (ndp[y] + c * k) % MOD
        else:
            z = y % s
            ndp[y] = (ndp[y] + c * (k - 1)) % MOD
            if z < ms:
                ans = (ans + z * c * factorials[k - 1]) % MOD
            else:
                ndp[z] = (ndp[z] + c) % MOD
    dp = ndp

for y, c in dp.items():
    ans = (ans + (y % ms) * c) % MOD

print(ans)

Submission status: Accepted

Solution code:
import math
import sys

sys.setrecursionlimit(100000000)
# 動的計画法とmemo化で解く。
N, X = map(int, input().split())
S = list(map(int, input().split()))
S.sort(reverse=True)


def memoize(f):  # メモ化関数
    table = [{} for _ in range(N+1)]

    def func(i, key):
        if key not in table[i]:
            table[i][key] = f(i, key)
        return table[i][key]
    return func


@memoize
def dfs(i, x):
    if i == N:
        return x
    else:
        return dfs(i+1, x % S[i]) + dfs(i+1, x) * (N-i-1)


print(dfs(0, X) % (10**9+7))

Submission status: Accepted

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

S.sort(reverse=True)
mod = 10**9+7
dp = [ [0] * (10**5+1) for _ in range(N+1)]
dp[0][X] = 1
for i in range(N):
    for j in range(0,10**5+1):
        dp[i+1][j] += dp[i][j] * (N-1-i) % mod
        dp[i+1][j% S[i]] += dp[i][j] 

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

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,x = map(int,input().split())
s = list(map(int,input().split()))
s.sort(reverse = True)
mod = 10**9+7

#dp[i][x]:s[i]まででxである場合の数
dp = [[0]*(x+1) for i in range(n+1)]
dp[0][x] = 1
for i,p in enumerate(s):
    for j in range(x+1):
        if dp[i][j] == 0:
            continue
        dp[i+1][j%p] += dp[i][j]
        dp[i+1][j] += dp[i][j]*(n-i-1)
        dp[i+1][j%p] %= mod
        dp[i+1][j] %= mod
res = 0
for i in range(1,x+1):
    res += dp[-1][i]*i
    res %= mod
print(res)

Submission status: Accepted

Solution code:
N, X = map(int,input().split())
S = list(map(int,input().split()))
S.sort(reverse=True)
S = [0] + S # 1-indexed 
MOD = 10**9+7
dp = [[0]*(10**5+1) for i in range(N+1)]
dp[0][X] = 1
for i in range(N):
    for x in range(10**5+1):
        dp[i+1][x%S[i+1]] += dp[i][x]
        dp[i+1][x] += dp[i][x]*(N-(i+1))
        dp[i+1][x%S[i+1]] %= MOD
        dp[i+1][x] %= MOD
ans = 0
for x in range(10**5+1):
    ans += (x*dp[N][x])%MOD
print(ans%MOD)

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
MOD = 10**9 + 7

def main():
    N, X = list(map(int, input().split()))
    S = list(map(int, input().split()))
    S = sorted(S, reverse=True)

    dp = dd(int)
    dp[X] = 1
    for i in range(N):
        new = dd(int)
        for x in dp:
            xx = x % S[i]
            new[x] += dp[x] * (N-i-1)
            new[x] %= MOD
            new[xx] += dp[x]
            new[xx] %= MOD
        dp = new

    total = 0
    for x in dp:
        total += dp[x] * x
        total %= MOD
    print(total)

main()

Submission status: Accepted

Solution code:
#分かりやすい解説記事
#https://betrue12.hateblo.jp/entry/2019/03/31/084642

from collections import defaultdict as dd
mod=10**9+7
N,X=map(int,input().split())
S=sorted(list(map(int,input().split())),reverse=True)
#print(S)
d = dd(int)
d[X] = 1
for i in range(N):
    new = dd(int)
    for X in d:
        new[X] += d[X]*(N-i-1)
        new[X] %= mod
        #print(X,new[X])
        new[X%S[i]] += d[X]
        new[X%S[i]] %= mod
    d = new
ans = 0
for x in d:
    ans += x*d[x]
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
inpl = lambda: list(map(int,input().split()))
M = 10**9 + 7

N, X = inpl()
S = sorted(inpl())
P = defaultdict(lambda: -1)

def ModuloOperations(i, x):
    if i == 0:
        return x
    else:
        if P[(i,x)] < 0:
            P[(i,x)] = (ModuloOperations(i-1,x)*(i-1) + ModuloOperations(i-1, x % S[i-1])) % M
        return P[(i,x)]

print(ModuloOperations(N,X))

Submission status: Accepted

Solution code:
N,X,*S=map(int,open(0).read().split())
e=enumerate
d=range(X+1)
for i,s in e(sorted(S)):d=[(t*i+d[j%s])%(10**9+7)for j,t in e(d)]
print(d[-1])

Submission status: Accepted

Solution code:
MOD = 10**9+7
MAX = 10**5+1

n,x = map(int,input().split())
s =  list(map(int,input().split()))

fac = [1 for i in range(MAX)]
inv = [1 for i in range(MAX)]
for i in range(2,MAX):
    fac[i] = fac[i-1]*i%MOD
    inv[i] = MOD - inv[MOD%i]*(MOD // i)%MOD

s.sort()
dp = [0 for i in range(x+1)]
for i in range(x+1):dp[i] = (i%s[0])*fac[n-1]%MOD

for i in range(1,n):
    dpp = dp[:]
    for j in range(x+1):
        dpp[j] = (dp[j]+dp[j%s[i]]*inv[i])%MOD
    dp = dpp


print(dp[x])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
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 II(): return int(sys.stdin.readline())
def SI(): return input()
from math import factorial
from collections import Counter

def main():
    N, X = LI()
    S = LI()
    S.sort(reverse=True)
    dp = Counter()
    dp[X] = factorial(N)
    for i, s in enumerate(S):
        pre = dp
        dp = Counter()
        for n, cnt in pre.items():
            if s <= n:
                dp[n] += cnt * (N - 1 - i) // (N - i)
                dp[n % s] += cnt // (N - i)
            else:
                dp[n] += cnt
    ans = 0
    for n, cnt in dp.items():
        ans = (ans + (n * cnt) % MOD) % MOD

    return ans

print(main())

Submission status: Accepted

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

MOD = 10**9+7

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

for i,a in enumerate(S):
    for j in range(1,X+1):
        if dp[i][j] == 0: continue
        dp[i+1][j] += dp[i][j] * (N-1-i)
        dp[i+1][j] %= MOD
        dp[i+1][j%a] += dp[i][j]
        dp[i+1][j%a] %= MOD

ans = sum(i*a for i,a in enumerate(dp[-1]))
print(ans % MOD)

Submission status: Accepted

Solution code:
from functools import lru_cache
N, X = map(int, input().split())
S = sorted([int(a) for a in input().split()])[::-1]
P = 10**9+7
fact = [1]
for i in range(N+10):
    fact.append(fact[-1]*(i+1)%P)

@lru_cache(None)
def calc(k, x):
    if k >= N:
        return x
    if x < S[-1]:
        return (x*fact[N-k]) % P
    return (calc(k+1, x%S[k]) + calc(k+1, x) * (N-k-1)) % P

print(calc(0, X))

Submission status: Accepted

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

Factorial=[1]*(N+1)
for i in range(1,N+1):
  Factorial[i]=Factorial[i-1]*(i)%mod
def power(x,y):
  if y==0:
    return 1
  elif y==1:
    return x%mod
  elif y%2==0:
    return power(x,y//2)**2%mod
  else:
    return ((power(x,y//2)**2)*x)%mod
inv=[0]*(N+1)
for i in range(N+1):
  inv[i]=power(i,mod-2)
dp=[[0]*(X+1) for i in range(N+1)]
for x in range(X+1):
  dp[N][x]=x
for i in range(N)[::-1]:
  for x in range(X+1):
    dp[i][x]=dp[i+1][x%S[i]]+(N-i-1)*dp[i+1][x]
    dp[i][x]%=mod
print((dp[0][X])%mod)

Submission status: Accepted

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

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

S.sort(reverse=True)

DP={X:1}

for i in range(N):
    s=S[i]
    
    NDP=dict()

    for d in DP:
        if d<s:
            NDP[d]=(NDP.get(d,0)+DP[d]*(N-i))%mod

        else:
            NDP[d]=(NDP.get(d,0)+DP[d]*(N-i-1))%mod
            NDP[d%s]=(NDP.get(d%s,0)+DP[d])%mod

    DP=NDP

SUM=0
for d in DP:
    SUM=(SUM+d*DP[d])%mod

print(SUM)

Submission status: Accepted

Solution code:
from collections import defaultdict
N,X=map(int,input().split())
S=[int(i) for i in input().split()]
S=sorted(S,reverse=True)
mod=10**9+7
P=[1]*(N+1)#1/i
for i in range(1,N+1):
    P[i]=pow(i,mod-2,mod)
#print(P)
dd=defaultdict(int)
dd[X]=1
for i in range(N):
    ndd=defaultdict(int)
    for x,p in dd.items():
        ndd[x]+=((1-P[N-i])*p)
        ndd[x]%=mod
        ndd[x%S[i]]+=(P[N-i]*p)
        ndd[x%S[i]]%=mod
    dd=ndd
    #print(dd)
t=1
table=[1]*(N+3)
for i in range(1,N+3):
    t*=i
    t%=mod
    table[i]=t
ans=0
for x,p in dd.items():
    ans+=(x*p*table[N])%mod
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
mod = 10**9+7
n,x = map(int, input().split())
s = sorted(list(map(int, input().split())),reverse=True)
d = dd(int)
d[x] = 1
for i in range(n):
    new = dd(int)
    for x in d:
        new[x] += d[x]*(n-i-1)
        new[x] %= mod
        new[x%s[i]] += d[x]
        new[x%s[i]] %= mod
    d = new
ans = 0
for x in d:
    ans += x*d[x]
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
N, X = map(int, input().split())
*V, = map(int, input().split())

MOD = 10**9 + 7

V.sort()

S = [0]*(X+1)
S[X] = 1
T = [0]*(X+1)
zeros = [0]*(X+1)
for i in range(N-1, -1, -1):
    T[:] = zeros
    for k in range(X+1):
        S[k] %= MOD
        T[k] += S[k] * i % MOD
        T[k % V[i]] += S[k]
    S, T = T, S
print(sum(k*S[k] % MOD for k in range(V[0])) % MOD)

Submission status: Accepted

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

fact_memo = [0]*201
fact_memo[0] = 1
def fact(n):
    if fact_memo[n] == 0:
        fact_memo[n] = n*fact(n-1)%mod
    return fact_memo[n]

fact_inv_memo = [0]*201
fact_inv_memo[0] = 1
def fact_inv(n):
    if fact_inv_memo[n] == 0:
        fact_inv_memo[n] = pow(fact(n),mod-2,mod)
    return fact_inv_memo[n]

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

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

Submission status: Accepted

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] = 1
    for i in range(n):
        c = a[i]
        e = collections.defaultdict(int)
        for k,v in d.items():
            e[k] += v * (n-i-1)
            e[k] %= mod
            e[k%c] += v
            e[k%c] %= mod

        d = e

    r = 0
    for k,v in d.items():
        r += k * v
        r %= mod

    return r


print(main())

Submission status: Accepted

Solution code:
def int_raw():
    return int(raw_input())

def ss_raw():
    return raw_input().split()

def ints_raw():
    return map(int, ss_raw())

INF = 1 << 29
DIV = 10**9 +7
N,X  = ints_raw()
dp = [{} for x in xrange(X+1)]

Ss = ints_raw()

Ss.sort()


def rec(n,idx):
    if idx == 0:
        return n%Ss[0]
    elif idx in dp[n]:
        return dp[n][idx]
    else:
        ans = (rec(n,idx-1)*idx + rec(n%Ss[idx],idx-1))%DIV
        dp[n][idx]=ans
        return ans

def ans():
    return rec(X,N-1)

print ans()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
mod=10**9+7
n,x=map(int,input().split())
S=list(map(int,input().split()))
S.sort()
DP=[[0]*(x+1) for _ in range(n+1)]
for i in range(x+1):
    DP[1][i]=i%S[0]
for i in range(1,n):
    for j in range(x+1):
        DP[i+1][j]=(DP[i][j]*i+DP[i][j%S[i]])%mod
print(DP[n][x])

Submission status: Accepted

Solution code:
N, X = map(int, input().split())
*V, = map(int, input().split())

MOD = 10**9 + 7

fact = [1]*(X+1)
rfact = [1]*(X+1)
for i in range(X):
    fact[i+1] = r = fact[i] * (i+1) % MOD
    rfact[i+1] = pow(r, MOD-2, MOD)

V.sort()

S = [0]*(X+1)
S[X] = 1
for i in range(N-1, -1, -1):
    T = [0]*(X+1)
    for k in range(X+1):
        S[k] %= MOD
        T[k] += S[k] * i % MOD
        T[k % V[i]] += S[k]
    S = T
print(sum(k*S[k] % MOD for k in range(V[0])) % MOD)

Submission status: Accepted

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: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
#define INF_LL 1LL << 39
#define INF 100000000
#define MOD 1000000007LL
#define ll long long
#define all(x) x.begin(), x.end()
#define REP(i, a, b) for(int i = a; i < b; i++)
#define rep(i, n) REP(i, 0, n)
#define prique priority_queue
#define PI acos(-1)
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<ll> vl;
typedef vector<vector<int>> matrix;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int sign[2] = {1, -1};
template <class T> bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T> bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return 1;
    }
    return 0;
}
struct edge {
    int to, cost;
};

ll dp[202][100010];

signed main() {
    int n, x;
    cin >> n >> x;
    vi s(n);
    rep(i, n) cin >> s[i];
    sort(all(s), greater<int>());
    dp[0][x] = 1;
    rep(i, n) REP(j, 0, x + 1) {
        dp[i + 1][j % s[i]] += dp[i][j];
        dp[i + 1][j] += dp[i][j] * (n - i - 1);
        dp[i + 1][j] %= MOD;
    }
    // rep(i, n + 1) {
    //     rep(j, x + 1) cout << dp[i][j] << " ";
    //     cout << endl;
    // }
    ll res = 0;
    REP(i, 1, x + 1) {
        res += dp[n][i] * i;
        res %= MOD;
    }
    cout << res << endl;
}

Submission status: Runtime Error

Solution code:
import math
import os
import sys
from functools import lru_cache

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

S.sort()


# @lru_cache(maxsize=None)
# def test2(x, si):
#     # S[si] を最初にとったとき、最終的な数値の期待値
#     if si == 0:
#         return x % S[si]
#
#     ret = 0
#     for j in range(si):
#         ret += test2(x % S[si], si=j)
#     return ret / si
#
#
# dp = np.zeros((N, X + 1))
# dp[0] = np.arange(X + 1) % S[0]
# for i in range(1, N):
#     for x in range(X + 1):
#         dp[i][x] = np.mean(dp[:i, x % S[i]])
# print(dp[:, X])
# print(dp[:, X].sum() * math.factorial(N) / N % MOD)


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


@lru_cache(maxsize=None)
def rec(x, i):
    if i == 0:
        return x % S[0]
    ret = 0
    for j in range(i):
        ret += rec(x % S[i], j)
    return ret / i


recsum = sum([rec(X, i) for i in range(N)])
print(round(recsum * math.factorial(N) / N % MOD))

Submission status: Runtime Error

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

S.sort()


# @lru_cache(maxsize=None)
# def test2(x, si):
#     # S[si] を最初にとったとき、最終的な数値の期待値
#     if si == 0:
#         return x % S[si]
#
#     ret = 0
#     for j in range(si):
#         ret += test2(x % S[si], si=j)
#     return ret / si


# dp = np.zeros((N, X + 1))
# dp[0] = np.arange(X + 1) % S[0]
# for i in range(1, N):
#     for x in range(X + 1):
#         dp[i][x] = np.mean(dp[:i, x % S[i]])
# print(dp[:, X].sum() * math.factorial(N) / N % MOD)


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

Submission status: Runtime Error

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

S.sort()


# @lru_cache(maxsize=None)
# def test2(x, si):
#     # S[si] を最初にとったとき、最終的な数値の期待値
#     if si == 0:
#         return x % S[si]
# 
#     ret = 0
#     for j in range(si):
#         ret += test2(x % S[si], si=j)
#     return ret / si


# dp = np.zeros((N, X + 1))
# dp[0] = np.arange(X + 1) % S[0]
# for i in range(1, N):
#     for x in range(X + 1):
#         dp[i][x] = np.mean(dp[:i, x % S[i]])
# print(dp[:, X].sum() * math.factorial(N) / N % MOD)


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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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][x] * i #% MOD

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

Submission status: Runtime Error

Solution code:
import itertools
import math
input = raw_input

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

c = 0
def perm(lst,x):
    if len(lst) == 0:
        return x
    else:
        cc = 0
        for i in range(len(lst)):
            lst2 = lst[:]
            lst2.pop(i)
            if x % lst[i] < min(lst2):
                cc += (x % lst[i]) * math.factorial(len(lst2))
            else:
                cc += perm(lst2, x % lst[i])
        return cc

print(perm(s,X) % 1000000007)

Submission status: Runtime Error

Solution code:
import math

n,x = map(int,input().split())
s = sorted(list(map(int,input().split())),reverse = True)
mod = 10**9+7
memo = {}

def f(i,x):
    if str(i) + 's' + str(x) in memo:
        return memo[str(i) + 's' + str(x)]
    if i == 0:
        return x
    if x == 0:
        return 0
    else:
        a = f(i-1,x) * (1 - 1/i)+ f(i-1,x%s[n-i]) / i
        memo[str(i) + 's' + str(x)] = a
        return a

print(int(f(n,x) * math.factorial(n)) % mod)

Submission status: Runtime Error

Solution code:
import math

n,x = map(int,input().split())
s = sorted(list(map(int,input().split())),reverse = True)
mod = 10**9+7
memo = {}

def f(i,x):
    if str(i) + str(x) in memo:
        return memo[str(i) + str(x)]
    if i == 0:
        return x
    if x == 0:
        return 0
    else:
        a = f(i-1,x) * (1 - 1/i)+ f(i-1,x%s[n-i]) / i
        memo[str(i) + str(x)] = a
        return a

print(int(f(n,x) * math.factorial(n)) % mod)

Submission status: Runtime Error

Solution code:
n,x = map(int,input().split())
s = sorted(list(map(int,input().split())),reverse = True)
mod = 10**9+7
memo = {}

def f(i,x):
    if str(i) + str(x) in memo:
        return memo[str(i) + str(x)]
    if i == 0:
        return x
    if x == 0:
        return 0
    else:
        a = f(i-1,x) * (1 - 1/i)+ f(i-1,x%s[n-i]) / i
        memo[str(i) + str(x)] = a
        return a

print(int(f(n,x) * math.factorial(n)) % mod)

Submission status: Runtime Error

Solution code:
import math

n,x = map(int,input().split())
s = sorted(list(map(int,input().split())),reverse = True)
mod = 10**9+7

def f(i,x):
    if i == 0:
        return x
    if x == 0:
        return 0
    else:
        a = f(i-1,x) * (1 - 1/i)+ f(i-1,x%s[n-i]) / i
        memo[i,x] = a
        return a

print(int(f(n,x) * math.factorial(n)) % mod)

Submission status: Runtime Error

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]
        print("new_dp", new_dp)

    dp = new_dp

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

total %= mod

print(total)

Submission status: Runtime Error

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

#[N,X] = [10, 100000]
#S = [50001, 50000, 50002, 50003, 50004, 50005, 50006, 50007, 50008, 50009]


#DP(i,x) i回目で現在x

#initial

DP = np.array([[float(0)]*(X+1)]*(N+1))
DP[N] = [i for i in range(X+1)]
for i in range(N-1,-1,-1):
    for x in range(X+1):
        S_temp = [i for i in S if i <= x]
        if len(S_temp) == 0:
            DP[i][x] = DP[i+1][x]
        else:
            for j in range(len(S_temp)):
                DP[i][x] += DP[i+1][x%S_temp[j]]
            DP[i][x] = DP[i][x] / len(S_temp)
ans = DP[0][X]            
for i in range(1,N+1):
    ans = (ans*i)%(10**9+7)

print(int(ans))

Submission status: Runtime Error

Solution code:

import math
import sys

sys.setrecursionlimit(100000000)
# 動的計画法とmemo化で解く。
N, X = map(int, input().split())
S = list(map(int, input().split()))
S.sort(reverse=True)


def memoize(f):  # メモ化関数
    table = [{} for _ in range(N+1)]

    def func(i, key):
        if key not in table[i]:
            table[i][key] = f(i, key)
        return table[i][key]
    return func


@memoize
def dfs(i, x):
    if i == N:
        return x
    else:
        p = 1/(N-i)
        return dfs(i+1, x % S[i]) * p + dfs(i+1, x) * (1-p)


print(int((dfs(0, X) * math.factorial(N))) % (10**9+7))

Submission status: Runtime Error

Solution code:
import math
import sys

sys.setrecursionlimit(100000000)
# 動的計画法とmemo化で解く。
N, X = map(int, input().split())
S = list(map(int, input().split()))
S.sort(reverse=True)


def memoize(f):  # メモ化関数
    table = [{} for _ in range(N+1)]

    def func(i, key):
        if key not in table[i]:
            table[i][key] = f(i, key)
        return table[i][key]
    return func


@memoize
def dfs(i, x):
    if i == N:
        return x
    else:
        p = 1/(N-i)
        return dfs(i+1, x % S[i]) * p + dfs(i+1, x) * (1-p)


print((int(dfs(0, X) * math.factorial(N))) % (10**9+7))

Submission status: Runtime Error

Solution code:
import math
# 動的計画法とmemo化で解く。
N, X = map(int, input().split())
S = list(map(int, input().split()))
S.sort(reverse=True)


def memoize(f):  # メモ化関数
    table = [{} for _ in range(N+1)]

    def func(i, key):
        if key not in table[i]:
            table[i][key] = f(i, key)
        return table[i][key]
    return func


@memoize
def dfs(i, x):
    if i == N:
        return x
    else:
        p = 1/(N-i)
        return dfs(i+1, x % S[i]) * p + dfs(i+1, x) * (1-p)


print((int(dfs(0, X) * math.factorial(N))) % (10**9+7))

Submission status: Runtime Error

Solution code:
N,X,*S=map(int,open(0).read().split())
e=enumerate
d=range(X+1)
for i,s in e(sorted(S)):d=[(t*i+x[j%s])%(10**9+7)for j,t in e(d)]
print(d[-1])

Submission status: Runtime Error

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

from itertools import permutations
from multiprocessing import Pool
import multiprocessing as multi

n, x = map(int, input().split())
s = list(map(int, input().split()))


def process(s_l):
    xx = x
    for ss in s_l:
        if xx < ss:
            continue
        xx = xx % ss
    return xx


p = Pool(multi.cpu_count())
result = p.map(process, [s_p for s_p in permutations(s)])
p.close()

print(sum(result) % 1000000007)

Submission status: Runtime Error

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

fact_memo = [0]*201
fact_memo[0] = 1
def fact(n):
    if fact_memo[n] == 0:
        fact_memo[n] = n*fact(n-1)%mod
    return fact_memo[n]

fact_inv_memo = [0]*201
fact_inv_memo[0] = 1
def fact_inv(n):
    if fact_inv_memo[n] == 0:
        fact_inv_memo[n] = pow(fact(n),mod-2,mod)
    return fact_inv_memo[n]

dp = defaultdict(lambda :-1)

def rec(n,x):
    if dp[(n,x)] != -1:
        return dp[(n,x)]
    if n == 0:
        dp[(n,x)] = x%S[0]
        return dp[(n,x)]
    s = S[:n+1]
    if x <= s[-1]:
        k = bisect.bisect(s,x)
        if k == 0:
            dp[(n,x)] = x*fact(n+1)%mod
        else:
            dp[(n,x)] = fact(n+1)*fact_inv(k)*rec(k-1,x)%mod
    else:
        res = x%s[0]*fact(n)%mod
        for i in range(1,n+1):
            res += fact(n)*fact_inv(i)*rec(i-1,x%s[i])%mod
        dp[(n,x)] = res%mod
    return dp[(n,x)]
        
print(rec(N-1,X))

Submission status: Runtime Error

Solution code:
keep_list = []
main_dic={}

for i in range(N):
    keep_list.append([])
    main_dic.setdefault(i,[])
    middle_dic={}
    for moji in s_list:
        if i==0:
            left=X%moji
            middle_dic[str(moji)]=X%moji
        else:
            key_list=main_dic[i-1][0].keys()
            for key_moji in key_list:
                key_moji_list=key_moji.split(',')
                if (str(moji) in key_moji_list)==False:
                    now_moji=key_moji+','+str(moji)
                    middle_dic[str(now_moji)]=main_dic[i-1][0][key_moji]%moji
        #print(middle_dic)
    main_dic.setdefault(i,[]) 
    main_dic[i].append(middle_dic)
#print(main_dic)
print(sum(main_dic[N-1][0].values())%(10**9+7))

Submission status: Runtime Error

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

n1, n2 = map(int, input().split())
s = [int(i) for i in input().split()]

s.sort()

min_s = s[0]

i = n1-1
fac = math.factorial(i)

ss = sum([n2 % s[i] for i in range(len(s)) if n2 % s[i] < min_s]) * fac

l = [n2 % s[i] for i in range(len(s)) if n2 % s[i] > min_s]

while (l != []):
    ll = []
    for n2 in l:
        i -= 1
        fac = math.factorial(i)
        ss += sum([n2 % s[i] for i in range(len(s)) if s[i] < n2 and n2 % s[i] < min_s])*fac
        li = [n2 % s[i] for i in range(len(s)) if s[i] < n2 and n2 % s[i] > min_s]
        ll.extend(li)
    l = ll

ss%=1000000007

print(ss)

Submission status: Runtime Error

Solution code:
N, X = map(int, input().split())
SS = input()
S = SS.split(" ")
count = 0

for i in range(N):
    S[i] = int(S[i])

S.sort()
if S[0] != 1:
    Smin = S[0]

else:
    Smin = S[1]

def copy(s):
    ss = []
    for i in s:
        ss.append(i)
    
    return ss

def a(S, n, X):
    global count
    if X < Smin:
        c = 1
        for i in range(1, len(S) + 1):
            c *= i
        count += X * c
        return
    for i in range(n):
        s = copy(S)
        b = s.pop(i)
        if len(s) == 0:
            count += X % b
        else:
            a(s, n - 1, X % b)

a(S, N, X)

print(count % (10 ** 9 + 7))

Submission status: Runtime Error

Solution code:
import itertools
N,X=input().split()
N=int(N)

t=[]
d=[]
for i in range(N):
    t[i],d[i]= input().split()
a=list(itertools.permutations(range(N)))
answer=0
kotae=X
for narabi in a:
    for waru in narabi:
        kotae=kotae%waru
    answer+=kotae
    kotae=X

answer=answer%100000009

print(answer+"\n")