結果
問題 | No.2243 Coaching Schedule |
ユーザー | titia |
提出日時 | 2023-03-12 00:41:44 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,546 ms / 4,000 ms |
コード長 | 2,903 bytes |
コンパイル時間 | 279 ms |
コンパイル使用メモリ | 81,704 KB |
実行使用メモリ | 130,604 KB |
最終ジャッジ日時 | 2023-10-18 10:23:51 |
合計ジャッジ時間 | 21,264 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 73 ms
91,220 KB |
testcase_01 | AC | 73 ms
91,220 KB |
testcase_02 | AC | 73 ms
91,220 KB |
testcase_03 | AC | 73 ms
91,220 KB |
testcase_04 | AC | 72 ms
91,220 KB |
testcase_05 | AC | 298 ms
130,604 KB |
testcase_06 | AC | 453 ms
122,496 KB |
testcase_07 | AC | 449 ms
122,500 KB |
testcase_08 | AC | 434 ms
122,500 KB |
testcase_09 | AC | 562 ms
119,332 KB |
testcase_10 | AC | 563 ms
119,332 KB |
testcase_11 | AC | 564 ms
119,332 KB |
testcase_12 | AC | 2,546 ms
116,208 KB |
testcase_13 | AC | 2,216 ms
116,424 KB |
testcase_14 | AC | 2,242 ms
116,424 KB |
testcase_15 | AC | 2,214 ms
116,424 KB |
testcase_16 | AC | 243 ms
116,736 KB |
testcase_17 | AC | 195 ms
108,556 KB |
testcase_18 | AC | 351 ms
118,800 KB |
testcase_19 | AC | 510 ms
117,744 KB |
testcase_20 | AC | 453 ms
110,400 KB |
testcase_21 | AC | 247 ms
111,984 KB |
testcase_22 | AC | 230 ms
111,984 KB |
testcase_23 | AC | 125 ms
103,920 KB |
testcase_24 | AC | 296 ms
114,096 KB |
testcase_25 | AC | 135 ms
103,920 KB |
testcase_26 | AC | 171 ms
108,084 KB |
testcase_27 | AC | 327 ms
114,096 KB |
testcase_28 | AC | 139 ms
104,448 KB |
testcase_29 | AC | 408 ms
114,888 KB |
testcase_30 | AC | 420 ms
123,552 KB |
testcase_31 | AC | 429 ms
125,140 KB |
testcase_32 | AC | 238 ms
109,936 KB |
testcase_33 | AC | 180 ms
109,144 KB |
testcase_34 | AC | 364 ms
117,264 KB |
testcase_35 | AC | 420 ms
118,536 KB |
testcase_36 | AC | 395 ms
123,552 KB |
ソースコード
import sys input = sys.stdin.readline from collections import Counter # FFT # mod=998244353 における、NTTによる高速フーリエ変換、畳み込み # 他の提出を参考にしており、あまり理解できていません…… mod=998244353 Weight=[1, 998244352, 911660635, 372528824, 929031873, 452798380, 922799308, 781712469, 476477967, 166035806, 258648936, 584193783, 63912897, 350007156, 666702199, 968855178, 629671588, 24514907, 996173970, 363395222, 565042129, 733596141, 267099868, 15311432, 0] Weight_inv=[1, 998244352, 86583718, 509520358, 337190230, 87557064, 609441965, 135236158, 304459705, 685443576, 381598368, 335559352, 129292727, 358024708, 814576206, 708402881, 283043518, 3707709, 121392023, 704923114, 950391366, 428961804, 382752275, 469870224, 0] def fft(A,n,h,inverse=0): if inverse==0: for i in range(h): m=1<<(h-i-1) for j in range(1<<i): w=1 ij=j*m*2 wk=Weight[h-i] for k in range(m): A[ij+k],A[ij+k+m]=(A[ij+k]+A[ij+k+m])%mod,(A[ij+k]-A[ij+k+m])*w%mod w=w*wk%mod else: for i in range(h): m=1<<i for j in range(1<<(h-i-1)): w=1 ij=j*m*2 wk=Weight_inv[i+1] for k in range(m): A[ij+k],A[ij+k+m]=(A[ij+k]+A[ij+k+m]*w)%mod,(A[ij+k]-A[ij+k+m]*w)%mod w=w*wk%mod if inverse==1: INV_n=pow(n,mod-2,mod) for i in range(n): A[i]=A[i]*INV_n%mod return A def convolution(A,B): FFTLEN=len(A)+len(B)-1 h=FFTLEN.bit_length() LEN=2**h A+=[0]*(LEN-len(A)) # A,Bのサイズを2ベキに揃える B+=[0]*(LEN-len(B)) A_FFT=fft(A,LEN,h) B_FFT=fft(B,LEN,h) for i in range(len(A)): A[i]=A[i]*B[i]%mod A=fft(A,LEN,h,1) return A[:FFTLEN] FACT=[1] for i in range(1,2*10**5+1): FACT.append(FACT[-1]*i%mod) FACT_INV=[pow(FACT[-1],mod-2,mod)] for i in range(2*10**5,0,-1): FACT_INV.append(FACT_INV[-1]*i%mod) FACT_INV.reverse() def Combi(a,b): if 0<=b<=a: return FACT[a]*FACT_INV[b]%mod*FACT_INV[a-b]%mod else: return 0 def Permutation(a,b): if 0<=a<b: return 0 return FACT[a]*FACT_INV[a-b]%mod M,N=map(int,input().split()) A=list(map(int,input().split())) C=Counter(A) C=Counter(C.values()) ANS=0 X=[] for i in range(N+1): if i%2==0: X.append(FACT_INV[i]) else: X.append(-FACT_INV[i]%mod) Y=[0]*(N+1) for i in range(N+1): x=FACT_INV[i] for c in C: x=x*pow(Permutation(i,c),C[c],mod)%mod Y[i]=x Z=convolution(X,Y) for K in range(N+1): ANS+=Z[K]*FACT[K]%mod ANS%=mod print(ANS)