結果
問題 | No.118 門松列(2) |
ユーザー | tonnnura172 |
提出日時 | 2020-05-07 10:05:54 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 137 ms / 5,000 ms |
コード長 | 1,234 bytes |
コンパイル時間 | 88 ms |
コンパイル使用メモリ | 11,032 KB |
実行使用メモリ | 18,352 KB |
最終ジャッジ日時 | 2023-09-16 07:47:30 |
合計ジャッジ時間 | 4,318 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 103 ms
17,512 KB |
testcase_01 | AC | 135 ms
18,352 KB |
testcase_02 | AC | 135 ms
18,100 KB |
testcase_03 | AC | 136 ms
18,028 KB |
testcase_04 | AC | 134 ms
18,344 KB |
testcase_05 | AC | 137 ms
18,024 KB |
testcase_06 | AC | 100 ms
17,156 KB |
testcase_07 | AC | 102 ms
17,108 KB |
testcase_08 | AC | 100 ms
17,256 KB |
testcase_09 | AC | 134 ms
18,164 KB |
testcase_10 | AC | 106 ms
17,668 KB |
testcase_11 | AC | 109 ms
17,792 KB |
testcase_12 | AC | 106 ms
17,660 KB |
testcase_13 | AC | 102 ms
17,668 KB |
testcase_14 | AC | 130 ms
18,240 KB |
testcase_15 | AC | 100 ms
17,416 KB |
testcase_16 | AC | 121 ms
17,796 KB |
testcase_17 | AC | 103 ms
17,616 KB |
testcase_18 | AC | 110 ms
17,736 KB |
testcase_19 | AC | 117 ms
17,844 KB |
testcase_20 | AC | 114 ms
17,740 KB |
testcase_21 | AC | 126 ms
18,272 KB |
testcase_22 | AC | 106 ms
17,500 KB |
testcase_23 | AC | 126 ms
18,200 KB |
testcase_24 | AC | 110 ms
17,756 KB |
testcase_25 | AC | 111 ms
17,648 KB |
ソースコード
import sys, re from collections import deque, defaultdict, Counter from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd, log from itertools import accumulate, permutations, combinations, product from operator import itemgetter, mul, add from copy import deepcopy from string import ascii_lowercase, ascii_uppercase, digits from bisect import bisect, bisect_left from heapq import heappush, heappop from functools import reduce, lru_cache def input(): return sys.stdin.readline().strip() def INT(): return int(input()) def MAP(): return map(int, input().split()) def LIST(): return list(map(int, input().split())) def ZIP(n): return zip(*(MAP() for _ in range(n))) sys.setrecursionlimit(10 ** 9) INF = float('inf') mod = 10 ** 9 + 7 N = INT() A = LIST() lim = 10**5+1 fact = [1] * (lim+1) fact_inv = [1] * (lim+1) for n in range(1, lim+1): fact[n] = (fact[n-1] * n) % mod fact_inv[lim] = pow(fact[lim], mod-2, mod) for n in range(lim, 0, -1): fact_inv[n-1] = (n * fact_inv[n]) % mod def C(n, r): return (((fact[n] * fact_inv[r]) % mod) * fact_inv[n-r]) % mod ans = C(N, 3) cnt_A = Counter(A) for v in Counter(A).values(): if v >= 3: ans -= C(v, 3) if v >= 2: ans -= C(v, 2)*(N-v) ans %= mod print(ans)