結果
問題 | No.1035 Color Box |
ユーザー |
![]() |
提出日時 | 2022-06-12 15:08:10 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 140 ms / 2,000 ms |
コード長 | 2,021 bytes |
コンパイル時間 | 288 ms |
コンパイル使用メモリ | 82,108 KB |
実行使用メモリ | 83,572 KB |
最終ジャッジ日時 | 2024-09-23 03:34:51 |
合計ジャッジ時間 | 3,808 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
import sysimport pypyjitimport itertoolsimport heapqimport mathfrom collections import deque, defaultdictimport bisectinput = sys.stdin.readlinesys.setrecursionlimit(10 ** 6)pypyjit.set_param('max_unroll_recursion=-1')def index_lt(a, x):'return largest index s.t. A[i] < x or -1 if it does not exist'return bisect.bisect_left(a, x) - 1def index_le(a, x):'return largest index s.t. A[i] <= x or -1 if it does not exist'return bisect.bisect_right(a, x) - 1def index_gt(a, x):'return smallest index s.t. A[i] > x or len(a) if it does not exist'return bisect.bisect_right(a, x)def index_ge(a, x):'return smallest index s.t. A[i] >= x or len(a) if it does not exist'return bisect.bisect_left(a, x)class Combination:def __init__(self, N, p):self.N = Nself.p = pself.f = [None] * (N + 1)self.finv = [None] * (N + 1)self.inv = [None] * (N + 1)self.f[0] = 1self.f[1] = 1self.finv[0] = 1self.finv[1] = 1self.inv[1] = 1for i in range(2, N + 1):self.f[i] = self.f[i - 1] * i % pself.inv[i] = p - self.inv[p % i] * (p // i) % pself.finv[i] = self.finv[i - 1] * self.inv[i] % pdef P(self, n, k):if n < k:return 0if n < 0 or k < 0:return 0return self.f[n] * self.finv[n - k] % self.pdef C(self, n, k):if n < k:return 0if n < 0 or k < 0:return 0return self.f[n] * (self.finv[k] * self.finv[n - k] % self.p) % self.p# 重複組合せ# n種類のものからk個選ぶdef H(self, n, k):return self.C(k + n - 1, k)N, M = map(int, input().split())mod = 10 ** 9 + 7comb = Combination(N, mod)ans = 0for i in range(M, 0, -1):if (M - i) & 1:ans -= comb.C(M, i) * pow(i, N, mod) % modelse:ans += comb.C(M, i) * pow(i, N, mod) % modans %= modprint(ans)