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 sys
input = sys.stdin.readline
mod = 10**9+7

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

B = [0]*(L+1) # i以下に何個あるか
for a in A:
    B[a] += 1
for i in range(L):
    B[i+1] += B[i]

NP = [1]
for n in range(1, N+1):
    NP.append(NP[-1]*n%mod)

C = [0]*(L+1)
C[X] = 1
for num in reversed(range(L+1)):
    if C[num] == 0: continue
    maxind = B[num]
    for ind in range(maxind):
        nnum = num%A[ind]
        nmaxind = B[nnum]
        C[nnum] = (C[nnum] + C[num]*NP[maxind-nmaxind-1]) % mod

ans = 0
for num in range(A[0]):
    ans = (ans + num*C[num]) % mod

print(ans)

Submission status: Wrong Answer

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

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

B = [0]*(L+1) # i以下に何個あるか
for a in A:
    B[a] += 1
for i in range(L):
    B[i+1] += B[i]

NP = [1]
for n in range(1, N+1):
    NP.append(NP[-1]*n%mod)

C = [0]*(L+1)
C[X] = 1
for num in reversed(range(L+1)):
    if C[num] == 0: continue
    maxind = B[num]
    for ind in range(maxind):
        nnum = num%A[ind]
        nmaxind = B[nnum]
        C[nnum] = (C[nnum] + NP[maxind-nmaxind-1]) % mod

ans = 0
for num in range(A[0]):
    ans = (ans + num*C[num]) % mod

print(ans)

Submission status: Wrong Answer

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

fact = [1] * 201
for i in range(200):
    fact[i + 1] = fact[i] * (i + 1)
    fact[i + 1] %= MOD

def solve(x, bit_state):
    res = 1
    cnt = 0
    for i in range(n):
        if s[i] > x and not((1 << i) & bit_state):
            bit_state |= (1 << i)
            cnt += 1
    res *= fact[cnt]
    res %= MOD
    if bit_state == 2 ** n - 1:
        return res * x
    ans = 0
    for i in range(n):
        if not((1 << i) & bit_state):
            ans += res * solve(x % s[i],  bit_state | (1 << i))
            ans %= MOD
    return ans
  
print(solve(x, 0))

Submission status: Wrong Answer

Solution code:
#  Copyright: this code was written at 2019. for AtCoder by Silviase
from functools import lru_cache


# lib
class ModInt:
    MOD = int(1e9 + 7)

    # int (演算子) ModIntはダメ

    def __init__(self, x):
        self.x = x % self.MOD

    # ModInt(op){ModInt, Int}に対応している
    def __add__(self, other):
        return self.__class__((self.x + other.x) % self.MOD) if isinstance(other, ModInt) else self.__class__(
            (self.x + other) % self.MOD)

    def __sub__(self, other):
        return self.__class__((self.x - other.x) % self.MOD) if isinstance(other, ModInt) else self.__class__(
            (self.x - other) % self.MOD)

    def __mul__(self, other):
        return self.__class__((self.x * other.x) % self.MOD) if isinstance(other, ModInt) else self.__class__(
            (self.x * other) % self.MOD)

    # 逆元をかけることに等しい
    def __truediv__(self, other):
        return self.__mul__(other.__inv__()) if isinstance(other, ModInt) else self.__mul__(ModInt(other).__inv__())

    # powは第三引数まで指定することで最適化される
    def __pow__(self, power, Modulo=MOD):
        return self.__class__(pow(self.x, power, Modulo))

    def __fac__(self):
        mx = ModInt(1)
        for i in range(self.x, 1, -1):
            mx = mx * i
        return mx

    # mi_C_kをModInt型で返す
    def __comb__(self, k):
        if isinstance(k, ModInt):
            if self < k:
                return ModInt(0)
            return self.__fac__() * k.__fac__().__inv__() * (self - k).__fac__().__inv__()
        else:
            if self < k:
                return ModInt(0)
            return self.__fac__() * ModInt(k).__fac__().__inv__() * ModInt(self.x - k).__fac__().__inv__()

    def __inv__(self):
        return self.__pow__(self.MOD - 2)

    def __str__(self):
        return str(self.x)

    def __lt__(self, other):
        return self.x < other.x if isinstance(other, ModInt) else self.x < other


@lru_cache(maxsize=100000)
# def
def calc(i, mod, dep):
    # print("calc(%d, %d, %d) was, called", i, mod, dep)
    if array[len(array) - 1] > mod:
        return ModInt(len(array) - dep).__fac__() * mod
    elif i == len(array) - 1:
        modres = mod % array[len(array) - 1]
        dep += 1
        return ModInt(len(array) - dep).__fac__() * modres
    elif array[i] > mod:
        return calc(i + 1, mod, dep)
    else:
        return calc(i + 1, mod, dep) + calc(i + 1, mod % array[i], dep + 1)


# 思考
# 降順ソートしたとき,i<jなるi,jについて,j->iの順に使っても結果はjと同じ
# つまり大きいものから使うかどうか決めていけば良さそう…？
# で,一番小さいものよりも小さくなったときもうそれは変わらない.
# なので残った数の階乗がいい感じに吐かれる
# 関数化する
# calc(x,y,z)
# x: 現在使うindex
# y: 現在の余り
# z: 深さ(というか使った数)
# 動作: calc(x,y,z) -> calc(x+1,y,z) と calc(x+1, y%array[x+1], z+1),もしくはy*(n-z)!
# 深すぎて死なないか? ->　modだしそんなに深くならないはず...少なくともyは半分になるから

# コード
n, x = map(int, input().split())
array = sorted(list(map(int, input().split())), reverse=True)

result = calc(0, x, 0)
print(result)

Submission status: Wrong Answer

Solution code:
#  Copyright: this code was written at 2019. for AtCoder by Silviase


# lib
class ModInt:
    MOD = int(1e9 + 7)

    # int (演算子) ModIntはダメ

    def __init__(self, x):
        self.x = x % self.MOD

    # ModInt(op){ModInt, Int}に対応している
    def __add__(self, other):
        return self.__class__((self.x + other.x) % self.MOD) if isinstance(other, ModInt) else self.__class__(
            (self.x + other) % self.MOD)

    def __sub__(self, other):
        return self.__class__((self.x - other.x) % self.MOD) if isinstance(other, ModInt) else self.__class__(
            (self.x - other) % self.MOD)

    def __mul__(self, other):
        return self.__class__((self.x * other.x) % self.MOD) if isinstance(other, ModInt) else self.__class__(
            (self.x * other) % self.MOD)

    # 逆元をかけることに等しい
    def __truediv__(self, other):
        return self.__mul__(other.__inv__()) if isinstance(other, ModInt) else self.__mul__(ModInt(other).__inv__())

    # powは第三引数まで指定することで最適化される
    def __pow__(self, power, Modulo=MOD):
        return self.__class__(pow(self.x, power, Modulo))

    def __fac__(self):
        mx = ModInt(1)
        for i in range(self.x, 1, -1):
            mx = mx * i
        return mx

    # mi_C_kをModInt型で返す
    def __comb__(self, k):
        if isinstance(k, ModInt):
            if self < k:
                return ModInt(0)
            return self.__fac__() * k.__fac__().__inv__() * (self - k).__fac__().__inv__()
        else:
            if self < k:
                return ModInt(0)
            return self.__fac__() * ModInt(k).__fac__().__inv__() * ModInt(self.x - k).__fac__().__inv__()

    def __inv__(self):
        return self.__pow__(self.MOD - 2)

    def __str__(self):
        return str(self.x)

    def __lt__(self, other):
        return self.x < other.x if isinstance(other, ModInt) else self.x < other


# def
def calc(i, mod, dep, array):
    if array[len(array) - 1] > mod:
        return ModInt(len(array) - dep).__fac__() * mod
    elif i == len(array) - 1:
        modres = mod % array[len(array) - 1]
        dep += 1
        return ModInt(len(array) - dep).__fac__() * modres
    else:
        return calc(i + 1, mod, dep, array) + calc(i + 1, mod % array[i], dep + 1, array)


# 思考
# 降順ソートしたとき,i<jなるi,jについて,j->iの順に使っても結果はjと同じ
# つまり大きいものから使うかどうか決めていけば良さそう…？
# で,一番小さいものよりも小さくなったときもうそれは変わらない.
# なので残った数の階乗がいい感じに吐かれる
# 関数化する
# calc(x,y,z)
# x: 現在使うindex
# y: 現在の余り
# z: 深さ(というか使った数)
# 動作: calc(x,y,z) -> calc(x+1,y,z) と calc(x+1, y%array[x+1], z+1),もしくはy*(n-z)!
# 深すぎて死なないか? ->　modだしそんなに深くならないはず...少なくともyは半分になるから

# コード
n, x = map(int, input().split())
ar = sorted(list(map(int, input().split())), reverse=True)

result = calc(0, x, 0, ar)
print(result)

Submission status: Wrong Answer

Solution code:
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]]
print(dp[N][X])

Submission status: Wrong Answer

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: Wrong Answer

Solution code:
import itertools

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

slist=list(map(int,input().split()))
slist.sort()
perm_N=list(itertools.permutations(range(N)))

dp = []
for _ in range(N+1):
  dp.append([0]*(X+1))
#print(dp)
dp[0][X] = 1
  
sum_mod = 0
hash_mod = {}
for perm in perm_N:
  xcopy = X
  for index in perm:
    xcopy %= slist[index]
    
  sum_mod += xcopy
  if xcopy not in hash_mod:
    hash_mod[xcopy] = 0
  hash_mod[xcopy] += 1
  
#print(sum_mod%mod)
#print(hash_mod)

for i in range(1,N+1):
  for s in slist:
    for j in range(X+1):
      dp[i][j%s] += dp[i-1][j]
  
all_sum = 0
#print(dp[N])
for i in range(X+1):
  all_sum += i*dp[N][i]
  
all_sum %= mod
print(all_sum)

Submission status: Wrong Answer

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


p = 0
for i in range(N):
    p += test2(X, i)
print(int(p * math.factorial(N) / N % MOD))

Submission status: Wrong Answer

Solution code:
import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import sys

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


def test(x, i):
    # S[i] が結果に影響したとき、最終的に j となる確率の配列
    if i == 0:
        ret = [0.0] * max(X, *S)
        ret[x % S[i]] = 1.0
        return np.array(ret)
    # 結果に影響するってことは、S[j<i] が全部このあとに入ってくる。
    ret = test(x % S[i], i=0)
    for j in range(1, i):
        ret += test(x % S[i], i=j)
    return ret / i


ans = 0
for i in range(N):
    ans += test(X, i) / N
print(np.dot(ans, range(len(ans))) * math.factorial(N) % MOD)

Submission status: Wrong Answer

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

frac = [0]*(n+1)
frac[0] = 1
for i in range(0,n):
    frac[i+1] = (i+1) * frac[i]
    frac[i+1] %= MOD

def solve(x, cnt, visited):
    ans = 0
    flag = False
    if cnt == n:
        return x
    for i in range(n):
        if not visited[i]:
            if s[i] <= x:
                if not flag:
                    ans += (x % s[i]) * frac[n - (cnt + 1)]
                    flag = True
                else:
                    tmp_visited = visited[0:]
                    tmp_visited[i] = True
                    ans += solve(x % s[i], cnt + 1, tmp_visited) % MOD
                    ans %= MOD
            else:
                tmp_visited = visited[0:]
                tmp_cnt = 0
                for j in range(i, n):
                    if not tmp_visited[j]:
                        tmp_visited[j] = True
                        tmp_cnt += 1
                ans += solve(x, cnt + tmp_cnt, tmp_visited) * frac[tmp_cnt] % MOD
                ans %= MOD
                break
    return ans
    
    
print(solve(x, 0, visited = [False]*n) % MOD)

Submission status: Wrong Answer

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 = dp.copy()
    for k, v in tmp_dp.items():
        tmp = k % n
        dp[k] = v * (N-i-1)
        dp[tmp] = dp.get(tmp, 0) + v
    #print(dp)
        
ans = 0
for k, v in dp.items():
    ans += k *  v

print(ans % MOD)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

import time
start = time.time()

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)
elapsed_time = time.time() - start
print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

Submission status: Wrong Answer

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 * i 
    dp = dp_n

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

Submission status: Wrong Answer

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 = None
for i, n  in enumerate(numbers):
    dp_n = np.zeros((X+1), dtype=int)
    dp_n += [dp[x % n] for x in range(X+1)]
    dp_n += dp * i 
    dp = dp_n

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

Submission status: Wrong Answer

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] = np.arange(X+1)

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

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

Submission status: Wrong Answer

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(dp[N][X] % MOD)

Submission status: Wrong Answer

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

numbers = S[:]

def dps(numbers, x):
    if len(numbers) == 1:
        return x % numbers[0]
    
    ret = 0
    for i, n in enumerate(numbers):
        x_mod = x % n
        if x_mod == 0 or x_mod == 1:
            ret += x_mod
        ret += dps(numbers[0:i] + numbers[i+1:], x_mod)
    return ret
        
ans = dps(numbers, X)
ans = ans % (10 ** 9 + 7)
print(ans)

Submission status: Wrong Answer

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:
        return f(i-1,x) * (1 - 1/i)+ f(i-1,x%s[n-i]) / i

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

Submission status: Wrong Answer

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

# nの階乗のリスト
def fact(n:int, mod:int) -> list:
    fac = [1,1]
    res = 1
    for i in range(2,n+1):
        res = res*i%mod
        fac.append(res)
    return fac

n, x = li()
s = list(li())

MOD = 10**9+7
fac = fact(n, MOD)

s.sort(reverse=True)

dp = [[0]*(x+1) for _ in range(n+1)]
dp[0][x] = 1

for i in range(n):
    for k in range(x+1):
        dp[i+1][k] += ((n-i-1)/(n-i)) * dp[i][k]
        dp[i+1][k%s[i]] += (1/(n-i)) * dp[i][k]
        
ans = sum([i*dp[n][i] for i in range(x+1)])
print(int(ans * fac[n]) % MOD)

Submission status: Wrong Answer

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)
if n <= 10000:
  print(9)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N, X = map(int, input().split())
S = sorted(list(map(int, input().split())))
dp = [[i % S[0] for i in range(X + 1)] for _ in range(N + 1)]
for i in range(1, N):
  for j in range(X + 1):
    dp[i][j] = dp[i - 1][j % S[i - 1]] + dp[i - 1][j] * i
print(dp[N - 1][X])

Submission status: Wrong Answer

Solution code:
from math import factorial
from functools import lru_cache

n, x = map(int, input().split())
s = list(map(int, input().split()))
s = sorted(s)
base = int(1e9 + 7)


@lru_cache(maxsize=100000)
def f(i, y):
    if y == 0:
        return 0
    if i < 0:
        return y
    return (i/(i + 1)) * f(i - 1, y) + (1/(i+1)) * f(i - 1, y % s[i])


result = ((f(n - 1, x) % base) * (factorial(n) % base)) % base

print(int(result))

Submission status: Wrong Answer

Solution code:
from math import factorial

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

t = [[0]*(x + 1)]*n
for i in range(x + 1):
    t[0][i] = i % s[0]
for j in range(1, n):
    for i in range(x + 1):
        t[j][i] = (j/(j + 1)) * t[j-1][i] + (1/(j + 1)) * t[j-1][i % s[j]]

base = int(1e9 + 7)
result = ((t[n - 1][x] % base) * (factorial(n) % base)) % base
print(int(result))

Submission status: Wrong Answer

Solution code:
from math import factorial
from functools import lru_cache

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


@lru_cache(maxsize=100000)
def f(i, y):
    if y == 0:
        return 0
    if i < 0:
        return y
    return (i/(i + 1)) * f(i - 1, y) + (1/(i+1)) * f(i - 1, y % s[i])

base = int(1e9 + 7)
result = ((f(n - 1, x) % base) * (factorial(n) % base)) % base
print(result)

Submission status: Wrong Answer

Solution code:
from math import factorial
from functools import lru_cache

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


@lru_cache(maxsize=n*x)
def f(i, y):
    if i < 0:
        return y
    return (i/(i + 1)) * f(i - 1, y) + (1/(i+1)) * f(i - 1, y % s[i])


base = int(1e9 + 7)
print(int(f(n - 1, x) * factorial(n) % base))

Submission status: Wrong Answer

Solution code:
from math import factorial

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


def f(i, y):
    if i < 0:
        return y
    return (i/(i + 1)) * f(i - 1, y) + (1/(i+1)) * f(i - 1, y % s[i])


base = int(1e9 + 7)
print(int(f(n - 1, x) * factorial(n)) % base)

Submission status: Wrong Answer

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
    print(i, s, dict(dp), ans)

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

print(ans)

Submission status: Wrong Answer

Solution code:
from math import factorial

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

a.sort(reverse=True)

MOD = 10 ** 9 + 7

dp = [[0.0 for _ in range(x+1)] for _ in range(n+1)]

dp[0][x] = 1.0

for i in range(n):
    for j in range(x+1):
        if dp[i][j] > 0:
            dp[i+1][j] += dp[i][j] * ((n-i-1) / (n-i))
            dp[i+1][j % a[i]] += dp[i][j] * (1 / (n-i))

ans = 0
for i in range(x+1):
    ans += dp[n][i] * i

print(int(ans * (factorial(n) % MOD)) % MOD)

Submission status: Wrong Answer

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 in range(n):
    for j in range(x+1):
        if dp[i][j] == 0:
            continue
        dp[i+1][j%s[i]] += dp[i][j]
        dp[i+1][j] += dp[i][j]*(n-i-1)
        if dp[i+1][j%s[i]] >= mod:
            dp[i+1][j%s[i]] -= mod
        if dp[i+1][j] >= mod:
            dp[i+1][j] -= mod
res = 0
for i in range(1,x+1):
    res += dp[-1][i]*i
    if res >= mod:
        res -= mod
print(res)

Submission status: Wrong Answer

Solution code:
mod = 10**9+7

n,m = map(int,input().split())

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

s.sort()

s = [None] + s

dp = [[0 for i in range(m+1)] for j in range(n+1)]
dp[1] = [i % s[1] for i in range(m+1)]

for i in range(2,n+1):
    for j in range(m+1):
        dp[i][j] = (dp[i-1][j] * (i-1) + dp[n-1][j%s[i]]) % mod
print(dp[n][m])

Submission status: Wrong Answer

Solution code:
mod = 10**9+7

n,m = map(int,input().split())

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

s.sort()

s = [None] + s

dp = [[0 for i in range(m+1)] for j in range(n+1)]
dp[1] = [i % s[1] for i in range(m+1)]

for i in range(2,n+1):
    for j in range(m+1):
        dp[i][j] = (dp[i-1][j] * (n-1) + dp[n-1][j%s[i]]) % mod
print(dp[n][m])

Submission status: Wrong Answer

Solution code:
import itertools
n,x = map(int,input().split())
s = list(input().split())
mod = 10**9+7
y = 0
p_list = list(itertools.permutations(s))

for a in p_list:
  for b in a:
    x = x%int(b)
  y += x

ans = y%mod
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
n,x = map(int,input().split())
s = list(input().split())
y = 0
p_list = list(itertools.permutations(s))
for a in p_list:
  for b in a:
    x = x%int(b)
    print(x)

Submission status: Wrong Answer

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: Wrong Answer

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 bisect import bisect
from functools import reduce

def func(x, arr):
    p = bisect(arr, x)
    if p < len(arr):
        x *= factorial(len(arr)) // factorial(p)
        x %= MOD
        arr = arr[:p]
    if len(arr) == 0:
        return x
    ret = 0
    for i in range(len(arr)):
        ret = (ret + func(x % arr[i], arr[:i] + arr[i + 1:])) % MOD
    return ret

def main():
    N, X = LI()
    S = LI()
    S.sort()
    ans = func(X, S)

    return ans

print(main())

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right as br
from functools import lru_cache
N, X = map(int, input().split())
S = sorted([int(a) for a in input().split()])
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 < 0:
        return x
    if x == S[0]:
        return 0
    if x < S[0]:
        return (x*fact[k+1]) % P
    a = br(S, x)
    if a < k:
        return (calc(a, x%S[k]) + calc(a, x) * fact[k]*pow(fact[a], P-2, P)) % P
    
    return (calc(k-1, x%S[k]) + calc(k-1, x) * k) % P

print(calc(N-1, X))

Submission status: Wrong Answer

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

def calc(k, x):
    if k < 0:
        return x
    if x == S[0]:
        return 0
    if x < S[0]:
        return (x*fact[k+1]) % P
    a = br(S, x)
    if a < k:
        return (calc(a, x%S[k]) + calc(a, x) * fact[k]*pow(fact[a], P-2, P)) % P
    
    return (calc(k-1, x%S[k]) + calc(k-1, x) * k) % P

print(calc(N-1, X))

Submission status: Wrong Answer

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

def calc(k, x):
    if k < 0:
        return x
    if x == S[0]:
        return 0
    if x < S[0]:
        return (x*fact[k+1]) % P
    a = min(br(S, x), k-1)
    return (calc(a, x%S[k]) + calc(a, x) * fact[k]*pow(fact[a], P-2, P)) % P

print(calc(N-1, X))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

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

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

for i in range(N-1,-1,-1):
	for x in range(x+1):
		table[x][i]=table[x][i+1]*(N-1-i)+table[x%a[i]][i+1] % MOD

print(table[x][0])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


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

    return factorials


n, x = map(int, input().split())
sss = sorted(map(int, input().split()), reverse=True)
MOD = 10 ** 9 + 7
m = sss[-1]
dp = [defaultdict(lambda: 0) for _ in [0] * (n + 1)]
dp[0][x] = 1
factorials = prepare(n - 1, MOD)
ans = 0
for i, s in enumerate(sss):
    for j in range(i, -1, -1):
        for k, c in dp[j].items():
            k %= s
            if k < m:
                ans += k * c * factorials[n - j - 1]
                ans %= MOD
            else:
                dp[j + 1][k] += c
print(ans)

Submission status: Wrong Answer

Solution code:
import math
N,X = map(int, input().split())
s_list = list(map(int, input().split())) # "1 2 3"と入力
keep_list = []
main_dic={}
pass_list=[]
pass_count=0
for i in range(N):
    keep_list.append([])
    main_dic.setdefault(i,[])
    middle_dic={}
    for moji in s_list:
        if i==0:
            middle_dic[str(moji)]=X%moji                
        else:
            key_list=main_dic[i-1][0].keys()
            for key_moji in key_list:
                if key_moji in pass_list:
                    continue
                key_moji_list=key_moji.split(',')
                if (str(moji) in key_moji_list)==False:
                    now_moji=key_moji+','+str(moji)
                    ans=main_dic[i-1][0][key_moji]%moji
                    middle_dic[str(now_moji)]=ans
                    if ans==1:
                        pass_list.append(str(now_moji))
                        pass_count+=1*math.factorial(N-(i+1))
    main_dic.setdefault(i,[]) 
    main_dic[i].append(middle_dic)
#print(pass_count)
#print(pass_list)
print(sum(main_dic[N-1][0].values())%(10**9+7))

Submission status: Wrong Answer

Solution code:
N, X = map(int, input().split())
S = [int(x) for x in input().split()]
S.sort(reverse=True)

def factorial_memo(n, p):
  F = [1] * (n + 1)
  for i in range(n):
    F[i + 1] = F[i] * (i + 1) % p
  return F

def inverse(F, p):
  Finv = [x for x in F]
  Finv[-1] = pow(Finv[-1], p - 2, p)
  for i in range(len(F) - 2, 0, -1):
    Finv[i] = Finv[i + 1] * (i + 1) % p
  return Finv

def comb(*A):
  f = F[sum(A)]
  for a in A:
    f *= Finv[a]
    f %= p
  return f

p = 10 ** 9 + 7
F = factorial_memo(2 * N, p)
Finv = inverse(F, p)

C = 0
def xUpdate(X, S):
  cnt = 0
  d = 0
  if len(S) == 0:
    return X
  if S[-1] > X:
    return X * F[len(S)]
  for i, s in enumerate(S):
    if s > X:
      d += 1
    else:
      cnt += xUpdate(X % s, S[d:i] + S[i+1:N]) * F[d] * comb(d, len(S))% p
  return cnt % p
print(xUpdate(X, S))