結果

問題 No.1629 Sorting Integers (SUM of M)
コンテスト
ユーザー yosaka
提出日時 2021-07-30 22:59:50
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,528 bytes
コンパイル時間 267 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 126,464 KB
最終ジャッジ日時 2024-09-16 02:55:40
合計ジャッジ時間 4,399 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 3
other TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

from itertools import combinations_with_replacement, permutations, combinations

# 逆元のテーブルを作成
def cmb(n, k, mod, fac, ifac):
    k = min(k, n - k)
    return fac[n] * ifac[k] * ifac[n - k] % mod


def make_tables(mod, n):
    fac = [1, 1]  # 階乗テーブル・・・(1)
    ifac = [1, 1]  # 逆元の階乗テーブル・・・(2)
    inverse = [0, 1]  # 逆元テーブル・・・(3)

    for i in range(2, n + 1):
        fac.append((fac[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod // i)) % mod)
        ifac.append((ifac[-1] * inverse[-1]) % mod)
    fac[0] = 0
    ifac[0] = 0
    return fac, ifac


def main():
    N = int(input())
    A = list(map(int, input().split()))
    lst = []
    for i in range(1, 10):
        lst += [i for _ in range(A[i - 1])]
    mod = 10 ** 9 + 7
    fac, ifac = make_tables(mod, 2 * 10 ** 5 + 10)
    ans = 0
    for perm in permutations(lst):
        # print(perm)
        for i in range(N):
            # ans += perm[i] * 10 ** i // A[perm[i - 1]]
            # print(perm[i], perm[i] - 1)
            if N != 1:
                ans += perm[i] * 10 ** i * (N - A[perm[i] - 1]) // A[perm[i] - 1]
            else:
                ans += perm[i] * 10 ** i
            ans %= mod
        # print(ans)
    # for i in range(1, 10):
    #     if A[i - 1] == 0:
    #         continue
    #     for j in range(N):
    #         ans += i * 10 ** j * (cmb(N, A[i - 1], mod, fac, ifac) // (N - A[i - 1]))
    #         ans %= mod
    print(ans)


main()
0