結果
問題 | No.3091 The Little Match Boy |
ユーザー |
|
提出日時 | 2025-04-06 15:48:50 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 96 ms / 2,000 ms |
コード長 | 1,360 bytes |
コンパイル時間 | 406 ms |
コンパイル使用メモリ | 81,792 KB |
実行使用メモリ | 100,096 KB |
最終ジャッジ日時 | 2025-04-06 15:48:57 |
合計ジャッジ時間 | 5,993 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 62 |
ソースコード
import sys input = lambda :sys.stdin.readline()[:-1] ni = lambda :int(input()) na = lambda :list(map(int,input().split())) yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES") no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO") ####################################################################### mod = 10 ** 9 + 7 nn = 10000 fact = [1] * nn for i in range(nn - 1): fact[i + 1] = fact[i] * (i + 1) % mod invfact = [1] * nn invfact[nn - 1] = pow(fact[nn - 1], mod - 2, mod) for i in range(nn - 1)[::-1]: invfact[i] = invfact[i + 1] * (i + 1) % mod def binom(x, y): if x < 0 or y < 0 or x - y < 0: return 0 return fact[x] * invfact[y] % mod * invfact[x - y] % mod ifs = [0] * nn for i in range(nn-1): ifs[i+1] = ifs[i] + invfact[i] def p(x, y): if x < y or x < 0: return 0 return fact[x] * invfact[x - y] % mod inf = 10 ** 9 B = 10 ** 6 + 10 def f(x, y): x, y = min(x, y), max(x, y) return x * B + y n, m = na() s = [i-1 for i in na()] q = [i for i in range(n)] ans = set() for i in range(m-1, -1, -1): q[s[i]], q[s[i]+1] = q[s[i]+1], q[s[i]] p = [i for i in range(n)] for i in range(m): q[s[i]], q[s[i]+1] = q[s[i]+1], q[s[i]] # print(p, q) ans.add(f(q[s[i]], q[s[i]+1])) p[s[i]], p[s[i]+1] = p[s[i]+1], p[s[i]] print(len(ans))