結果
問題 | No.1709 Indistinguishable by MEX |
ユーザー | puzneko |
提出日時 | 2021-11-05 01:30:34 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 298 ms / 2,000 ms |
コード長 | 1,038 bytes |
コンパイル時間 | 179 ms |
コンパイル使用メモリ | 81,964 KB |
実行使用メモリ | 116,068 KB |
最終ジャッジ日時 | 2024-10-15 08:07:16 |
合計ジャッジ時間 | 5,556 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
from sys import stdin n, *a = map(int, stdin.read().split()) p = 998244353 if n <= 2: print("{}".format(1)) exit() def powmod(n,pow,mod): val = 1 while pow > 0: if pow & 1: val = (val * n) % mod pow = pow >> 1 n = (n * n) % mod return val kaijo = [1 for i in range(n)] for i in range(1,n): kaijo[i] = kaijo[i-1] * i % p ichi = [0 for i in range(n)] for i in range(n): ichi[a[i]] = i left = ichi[0] right = ichi[1] if left > right: left, right = right, left anslist = [(right - left - 1,1)] for i in range(2,n): if ichi[i] < left: anslist.append((left - ichi[i] - 1,i)) left = ichi[i] elif ichi[i] > right: anslist.append((ichi[i] - right - 1,i)) right = ichi[i] last = 0 remained = 0 ans = 1 for range, ind in anslist: ans = ans * kaijo[remained] % p * powmod(kaijo[remained-(ind-last-1)],p-2,p) % p remained += range remained -= ind-last-1 last = ind ans = ans * kaijo[remained] % p print("{}".format(ans))