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

Solution code:

from math import factorial
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def ni(): return int(stdin.readline())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
N, X = tuple(li())
nums = list(li())
nums.sort()
MAGIC = 10 ** 9 + 7
total = 0
real = factorial(len(nums-1))
def helper(ops, target, facter):
    if not ops: return
    
    L = len(ops)
    global total
    global real
    for i, op in enumerate(ops):
        # factorial of nums > op
        new_f = factorial(L-1 - i)
        down_factor = new_f * facter
        if i == 0:
            res = target % op * real
            total += res
            total = total % MAGIC
            
        helper(ops[:i], target % op, down_factor)
helper(nums, X, 1)
print(total)

Submission status: Runtime Error

Solution code:

from math import factorial
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def ni(): return int(stdin.readline())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
N, X = tuple(li())
nums = list(li())
nums.sort()
MAGIC = 10 ** 9 + 7
total = 0
real = facterial(len(nums-1))
def helper(ops, target, facter):
    if not ops: return
    
    L = len(ops)
    global total
    global real
    for i, op in enumerate(ops):
        # factorial of nums > op
        new_f = factorial(L-1 - i)
        down_factor = new_f * facter
        if i == 0:
            res = target % op * real
            total += res
            total = total % MAGIC
            
        helper(ops[:i], target % op, down_factor)
helper(nums, X, 1)
print(total)

Submission status: Runtime Error

Solution code:
import itertools
def aa(board, ps, boards):
    if len(ps) == 1:
        boards += board%ps[0]
        for p in ps:
            new_ps = [e for e in ps if e >= p]
            return aa(board%p, new_ps)
n, x = (int(i) for i in input().split())  
s = [int(i) for i in input().split()]

final_ans = 0
max_s = max(s)
boards=0
aa(x,s,boards)
print(boards)

Submission status: Runtime Error

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

from itertools import permutations

from joblib import Parallel, delayed


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


def process(xx, s_l):
    for ss in s_l:
        xx = xx % ss
    return xx


result = Parallel(n_jobs=-1)([delayed(process)(x, s_p) for s_p in permutations(s)])

print(sum(result) % 1000000007)

Submission status: Runtime Error

Solution code:
import itertools

N,X = map(int, input().split())
S = [int(x) for x in input().split()]
New = list(itertools.permutations(S))

sum = 0
mod = 10 ** 9 + 7

for i in range(len(list(itertools.permutations(S)))):
    
    for j in range(N):
        alls = X % New[j][i]
        X = alls
    sum = sum + X

sum = sum % mod
print(sum)

Submission status: Runtime Error

Solution code:
import itertools
N, X = map(int, input().split())
S = []
d = X
sum = 0
for i in range(N):
    S.append(input())
for v in itertools.permutations(S, N):
    for i in N:
        d = d % v[i]
    sum += d
print(sum % (10^9+7)

Submission status: Runtime Error

Solution code:
import copy
import math
import bisect
N,X= map(int, input().split())
S=list(map(int,input().split()))
MOD=int(1e9 + 7)
S.sort()

def modsum(n,x,s):
  #print('modsum'+'n:'+str(n)+'x:'+str(x)+'s:'+str(s))
  if x==0:
    return 0
  elif n==1:
    return x % s[0]
  else:
    if x< min(s):
      return int(x*math.factorial(n))%MOD
    elif x < max(s):
      x_index = bisect.bisect_right(S,x)
      s_copy=copy.deepcopy(s)
      s_copy=s_copy[:x_index]
      #print('s_copy'+str(s_copy)+'x_i'+str(x_index))
      fact=int(math.factorial(n)/math.factorial(x_index))
      return (fact*modsum(x_index,x,s_copy))%MOD
    else:
      p=0
      for i in range(len(s)):
        s_copy=copy.deepcopy(s)
        s_copy.remove(s[i])
        p += modsum(n-1,x % s[i],s_copy) % MOD
      return p % MOD
  
print(modsum(N,X,S))

Submission status: Runtime Error

Solution code:
import math
from functools import lru_cache

@lru_cache(maxsize=10000)
def fact(n):
    return math.factorial(n)


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

tab = [0] * min(S)

S.sort()

@lru_cache(maxsize=10000)
def f(NUM, LIST):
    modL = [NUM % l for l in LIST]
    ret = 0
    for i in range(len(LIST)):
        l = modL[i]

        if l > min(S):
            newL = list(LIST)
            del newL[i]
            ret += f(l, newL)

        elif l == min(S):
            pass
        else:
            # ret += l * math.factorial(len(LIST) - 1)
            ret += l * fact(len(LIST) - 1)

    return ret% (10 ** 9 + 7)


print(f(X, tuple(S)) )

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

struct pairhash {
public:
  template <typename T, typename U>
  std::size_t operator()(const std::pair<T, U> &x) const
  {
    return std::hash<T>()(x.first) ^ std::hash<U>()(x.second);
  }
};

vector<int> s;
int mem[100001][201];

const int MOD = 1e9 + 7;

vector<int> pos;

long long dp(int x, int rem) {
  if (x == 0) {
    return 0;
  }
  if (mem[x][rem] != -1) { return mem[x][rem]; }
  int ans = 0;
  if (rem > 0) {
    ans = (dp(x, rem - 1) * rem) % MOD;
  }
  if (x < s[0]) {
    if (rem == 0) ans = x;
    //cerr << "go x: " << x << " rem: " << rem << " ans: " << ans << endl;
    return mem[x][rem] = ans;
  }

  for (int i = 0; i < s.size(); ++i) {
    if (s[i] > x) break;
    int xx = x % s[i];
    ans = ans + dp(xx, rem + pos[x] - pos[xx] - 1);
    while (ans >= MOD) ans -= MOD;
  }
  //cerr << "mem x: " << x << " rem: " << rem << " ans: " << ans << endl;
  return mem[x][rem] = ans;
}

int main() {
  memset(mem, -1, sizeof(mem));
  int n,x;
  cin >> n >> x;
  s.resize(n);
  for (auto& a : s) cin >> a;
  sort(s.begin(),s.end());
  int rem = 0;
  pos.resize(x + 1);
  int p = 0;
  for (int i = 0; i <= x; ++i) {
    while (p < s.size() && s[p] <= i) p++;
    pos[i] = p;
  }
  rem = s.size() - pos[x];
  //cerr << "rem: " << rem << endl;
  cout << dp(x, rem);
}

Submission status: Runtime Error

Solution code:
MOD = 10**9 + 7

def gen_candidate(N):
    for i in range(1 << (N-1)):
        bit = bin(i)[2:]
        bit = '0'*(N-1 - len(bit)) + bit
        yield bit+'1'

def main():
    N, X = list(map(int, input().split()))
    S = list(map(int, input().split()))
    S = sorted(S, reverse=True)
    total = 0
    for bit in gen_candidate(N):
        x = X
        for j, char in enumerate(bit):
            if int(char):
                x = x % S[j]
        num = 1
        num_one = 0
        num_zero = 0
        for b in reversed(bit):
            if int(b):
                num_one += 1
            else:
                num *= num_one + num_zero
                num_zero += 1
        total = (total + x * num) % MOD
    print(total)

main()

Submission status: Runtime Error

Solution code:
from sympy.ntheory.modular import crt, solve_congruence
import itertools

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

sum = 0
mod = 10 ** 9 + 7

for i in range len(list(itertools.permutations(S))):
    
    for j in range(N):
        alls = X % New[i][j]
        X = alls
    sum = sum + X


sum = sum % mod
print(sum)

Submission status: Runtime Error

Solution code:
#通るかな？
def 解():
    import numpy as np
    import sys
    input = sys.stdin.readline

    N,Q = [int(_) for _ in input().split()]

    S = input()
    dS = {}
    for i in range(1,N+1):
        s = S[i-1]
        if s in dS:
            dS[s].add(i)
        else:
            dS[s]={i}
    #aM = [1]*(N+2)
    #aM = {i:1 for i in range(N+2)}
    aM = np.array([1]*(N+2))

    for _ in range(Q):
        t,d = input().split()
        if t in dS:
            if d == "R":
                for i in dS[t]:
                    if aM[i]:
                        aM[i+1] += aM[i]
                        aM[i] = 0
            else:
                for i in dS[t]:
                    if aM[i]:
                        aM[i-1] += aM[i]
                        aM[i] = 0

    #print(sum(aM[i] for i in range(1,N+1)))
    print(sum(aM[1:N+1]))
解()

Submission status: Runtime Error

Solution code:
n,x = [int(i) for i in input().split()]
s = [int(i) for i in input().split()]

def solve(n,x,s):
    # if n==0: return 0
    if n==1:
        return x%s[0]
    ans = 0
    mod = [0]*n

    for i,si in enumerate(s):
        mod[i] = x % si

    for i,m in enumerate(mod):
        if m==0: continue
        if m < min(s):
            ans += fact(n-1) * m
            continue

        isans_0 = False
        for s_elem in s:
            isans_0 = True
            if m % s_elem == 0:
                break
        if isans_0: continue

        s_copy = s.copy()
        del(s_copy[i]) 
        ans += solve(n-1, m, s_copy)
    # print(x,s,ans)
    return ans % (1e9+7)

def fact(n):
    prod = 1
    for i in range(2,n+1):
        prod *= i
    return prod

print(int(solve(n,x,s) % (1e9+7)))

Submission status: Runtime Error

Solution code:
import math
n,x=map(int,input().split())
s=list(map(int,input().split()))
s.sort()
p=10**9+7
r=(((s[i]-1)*s[i])//2)%p
t=math.factorial(n-1)%p
print(r*t)

Submission status: Runtime Error

Solution code:
import copy
import math

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

ans = 0

def DFS(x,s_list):
    global ans
    if len(s_list) ==0:
        ans += x
    elif x < min(s_list):
        ans += x*math.factorial(len(s_list))
    elif x in s_list:
        ans += 0
    else:
        for i,s in enumerate(s_list.sort()):
          s_list_after = copy.deepcopy(s_list)
          s_list_after.pop(i)
          x_after = x%s
          DFS(x_after,s_list_after)
    
DFS(X,S_list)
print(ans% mod)

Submission status: Runtime Error

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


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


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

        next_X, next_cnt = X % s, cnt + 1

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

print(ans % MOD)

Submission status: Runtime Error

Solution code:
import itertools
import math

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

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

Submission status: Runtime Error

Solution code:
n, x = map(int,input().split())
s = list(map(int,input().split()))
p = list(itertools.permutations(s))
c = 0
for i in range(len(p)):
    f = x
    for j in range(n):
        f %= p[i][j]
        #print(p[i][j])
    c += f
    #print(f,c)
print(c%(pow(10, 9)+ 7))