結果

問題 No.389 ロジックパズルの組み合わせ
コンテスト
ユーザー はむ吉🐹
提出日時 2016-07-08 23:11:42
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 361 ms / 2,000 ms
コード長 944 bytes
コンパイル時間 185 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 118,656 KB
最終ジャッジ日時 2024-10-13 06:37:35
合計ジャッジ時間 11,115 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 99
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#!/usr/bin/env pypy3

import array

P = 10 ** 9 + 7


# Based on http://hos.ac/slides/20130319_enumeration.pdf
def main():
    m = int(input())
    hs = array.array("L", map(int, input().split()))
    if hs[0] == 0:
        print(1)
        return
    k = len(hs)
    s = sum(hs)
    if s + k - 1 > m:
        print("NA")
        return
    n = m + 1 - s
    inv = array.array("L", (0 for _ in range(n + 1)))
    inv[1] = 1
    for i in range(2, n + 1):
        inv[i] = P - (P // i) * inv[P % i] % P
    fac = array.array("L", (0 for _ in range(n + 1)))
    facinv = array.array("L", (0 for _ in range(n + 1)))
    fac[0] = 1
    facinv[0] = 1
    for i in range(1, n + 1):
        fac[i] = (fac[i - 1] * i) % P
        facinv[i] = (facinv[i - 1] * inv[i]) % P
    if not (0 <= k and k <= n):
        binom = 0
    else:
        binom = (((fac[n] * facinv[k]) % P) * facinv[n - k]) % P
    print(binom)


if __name__ == '__main__':
    main()
0