結果
問題 | No.389 ロジックパズルの組み合わせ |
ユーザー |
![]() |
提出日時 | 2022-02-06 19:35:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 274 ms / 2,000 ms |
コード長 | 3,662 bytes |
コンパイル時間 | 315 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 262,016 KB |
最終ジャッジ日時 | 2024-06-11 13:55:32 |
合計ジャッジ時間 | 23,565 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 99 |
ソースコード
def extgcd(a, b):if b:d, y, x = extgcd(b, a % b)y -= (a // b)*xreturn d, x, yreturn a, 1, 0class Combination:def __init__(self, n_max, mod=10**9+7):# O(n_max + log(mod))self.mod = modf = 1self.fac = fac = [f]for i in range(1, n_max+1):f = f * i % modfac.append(f)f = pow(f, mod-2, mod)self.facinv = facinv = [f]for i in range(n_max, 0, -1):f = f * i % modfacinv.append(f)facinv.reverse()# "n 要素を" は区別できる n 要素# "k グループ" はちょうど k グループdef __call__(self, n, r): # self.C と同じreturn self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.moddef C(self, n, r):if not 0 <= r <= n: return 0return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.moddef P(self, n, r):if not 0 <= r <= n: return 0return self.fac[n] * self.facinv[n-r] % self.moddef H(self, n, r):if (n == 0 and r > 0) or r < 0: return 0return self.fac[n+r-1] * self.facinv[r] % self.mod * self.facinv[n-1] % self.moddef rising_factorial(self, n, r): # 上昇階乗冪 n * (n+1) * ... * (n+r-1)return self.fac[n+r-1] * self.facinv[n-1] % self.moddef stirling_first(self, n, k): # 第 1 種スターリング数 lru_cache を使うと O(nk) # n 要素を k 個の巡回列に分割する場合の数if n == k: return 1if k == 0: return 0return (self.stirling_first(n-1, k-1) + (n-1)*self.stirling_first(n-1, k)) % self.moddef stirling_second(self, n, k): # 第 2 種スターリング数 O(k + log(n)) # n 要素を区別のない k グループに分割する場合の数if n == k: return 1 # n==k==0 のときのためreturn self.facinv[k] * sum((-1)**(k-m) * self.C(k, m) * pow(m, n, self.mod) for m in range(1, k+1)) % self.moddef balls_and_boxes_3(self, n, k): # n 要素を区別のある k グループに分割する場合の数 O(k + log(n))return sum((-1)**(k-m) * self.C(k, m) * pow(m, n, self.mod) for m in range(1, k+1)) % self.moddef bernoulli(self, n): # ベルヌーイ数 lru_cache を使うと O(n**2 * log(mod))if n == 0: return 1if n % 2 and n >= 3: return 0 # 高速化return (- pow(n+1, self.mod-2, self.mod) * sum(self.C(n+1, k) * self.bernoulli(k) % self.mod for k in range(n))) % self.moddef faulhaber(self, k, n): # べき乗和 0^k + 1^k + ... + (n-1)^k# bernoulli に lru_cache を使うと O(k**2 * log(mod)) bernoulli が計算済みなら O(k * log(mod))return pow(k+1, self.mod-2, self.mod) * sum(self.C(k+1, j) * self.bernoulli(j) % self.mod * pow(n, k-j+1, self.mod) % self.mod for j inrange(k+1)) % self.moddef lah(self, n, k): # n 要素を k 個の空でない順序付き集合に分割する場合の数 O(1)return self.C(n-1, k-1) * self.fac[n] % self.mod * self.facinv[k] % self.moddef bell(self, n, k): # n 要素を k グループ以下に分割する場合の数 O(k**2 + k*log(mod))return sum(self.stirling_second(n, j) for j in range(1, k+1)) % self.modmod = 10**9+7comb = Combination(1000000)m = int(input())h = list(map(int,input().split()))if len(h) == 1 and h[0] == 0:print(1)exit()P = sum(h) + len(h) - 1if P > m:print("NA")exit()a = comb.C(m - P + len(h),len(h))if a == 0:print("NA")else:print(a)