結果
問題 | No.2959 Dolls' Tea Party |
ユーザー |
![]() |
提出日時 | 2024-11-08 23:55:00 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,457 ms / 3,000 ms |
コード長 | 9,011 bytes |
コンパイル時間 | 216 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 137,408 KB |
最終ジャッジ日時 | 2024-11-08 23:56:12 |
合計ジャッジ時間 | 68,920 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 33 |
ソースコード
def make_divisors(n):lower_divisors , upper_divisors = [], []i = 1while i*i < n:if n % i == 0:lower_divisors.append(i)if i != n // i:upper_divisors.append(n//i)i += 1if i * i == n:lower_divisors.append(i)return lower_divisors + upper_divisors[::-1]def gcd(a, b):while a != 0:b %= aif b == 0: return aa %= breturn bmod = 998244353n = 10000inv = [1 for j in range(n + 1)]for a in range(2,n + 1):# ax + py = 1 <=> rx + p(-x-qy) = -q => x = -(inv[r]) * (p//a) (r = p % a)res = (mod - inv[mod % a]) * (mod // a)inv[a] = res % modfact = [1 for i in range(n + 1)]for i in range(1,n + 1):fact[i] = fact[i - 1] * i % modfact_inv = [1 for i in range(n + 1)]fact_inv[-1] = pow(fact[-1],mod - 2,mod)for i in range(n,0,-1):fact_inv[i - 1] = fact_inv[i] * i % modNTT_friend = [120586241,167772161,469762049,754974721,880803841,924844033,943718401,998244353,1045430273,1051721729,1053818881]NTT_dict = {}for i in range(len(NTT_friend)):NTT_dict[NTT_friend[i]] = iNTT_info = [[20,74066978],[25,17],[26,30],[24,362],[23,211],[21,44009197],[22,663003469],[23,31],[20,363],[20,330],[20,2789]]def popcount(n):c = (n&0x5555555555555555) + ((n>>1)&0x5555555555555555)c = (c&0x3333333333333333) + ((c>>2)&0x3333333333333333)c = (c&0x0f0f0f0f0f0f0f0f) + ((c>>4)&0x0f0f0f0f0f0f0f0f)c = (c&0x00ff00ff00ff00ff) + ((c>>8)&0x00ff00ff00ff00ff)c = (c&0x0000ffff0000ffff) + ((c>>16)&0x0000ffff0000ffff)c = (c&0x00000000ffffffff) + ((c>>32)&0x00000000ffffffff)return cdef topbit(n):h = n.bit_length()h -= 1return hdef prepared_fft(mod = 998244353):rank2 = NTT_info[NTT_dict[mod]][0]root,iroot = [0] * 30,[0] * 30rate2,irate2= [0] * 30,[0] * 30rate3,irate3= [0] * 30,[0] * 30root[rank2] = NTT_info[NTT_dict[mod]][1]iroot[rank2] = pow(root[rank2],mod - 2,mod)for i in range(rank2 - 1,-1,-1):root[i] = root[i + 1] * root[i + 1] % modiroot[i] = iroot[i + 1] * iroot[i + 1] % modprod,iprod = 1,1for i in range(rank2-1):rate2[i] = root[i + 2] * prod % modirate2[i] = iroot[i + 2] * iprod % modprod = prod * iroot[i + 2] % modiprod = iprod * root[i + 2] % modprod,iprod = 1,1for i in range(rank2-2):rate3[i] = root[i + 3] * prod % modirate3[i] = iroot[i + 3] * iprod % modprod = prod * iroot[i + 3] % modiprod = iprod * root[i + 3] % modreturn root,iroot,rate2,irate2,rate3,irate3root,iroot,rate2,irate2,rate3,irate3 = prepared_fft()def ntt(a):n = len(a)h = topbit(n)assert (n == 1 << h)le = 0while le < h:if h - le == 1:p = 1 << (h - le - 1)rot = 1for s in range(1 << le):offset = s << (h - le)for i in range(p):l = a[i + offset]r = a[i + offset + p] * rot % moda[i + offset] = (l + r) % moda[i + offset + p] = (l - r) % modrot = rot * rate2[topbit(~s & -~s)] % modle += 1else:p = 1 << (h - le - 2)rot,imag = 1,root[2]for s in range(1 << le):rot2 = rot * rot % modrot3 = rot2 * rot % modoffset = s << (h - le)for i in range(p):a0 = a[i + offset]a1 = a[i + offset + p] * rota2 = a[i + offset + p * 2] * rot2a3 = a[i + offset + p * 3] * rot3a1na3imag = (a1 - a3) % mod * imaga[i + offset] = (a0 + a2 + a1 + a3) % moda[i + offset + p] = (a0 + a2 - a1 - a3) % moda[i + offset + p * 2] = (a0 - a2 + a1na3imag) % moda[i + offset + p * 3] = (a0 - a2 - a1na3imag) % modrot = rot * rate3[topbit(~s & -~s)] % modle += 2def intt(a):n = len(a)h = topbit(n)assert (n == 1 << h)coef = inv[n]for i in range(n):a[i] = a[i] * coef % modle = hwhile le:if le == 1:p = 1 << (h - le)irot = 1for s in range(1 << (le - 1)):offset = s << (h - le + 1)for i in range(p):l = a[i + offset]r = a[i + offset + p]a[i + offset] = (l + r) % moda[i + offset + p] = (l - r) * irot % modirot = irot * irate2[topbit(~s & -~s)] % modle -= 1else:p = 1 << (h - le)irot,iimag = 1,iroot[2]for s in range(1 << (le - 2)):irot2 = irot * irot % modirot3 = irot2 * irot % modoffset = s << (h - le + 2)for i in range(p):a0 = a[i + offset]a1 = a[i + offset + p]a2 = a[i + offset + p * 2]a3 = a[i + offset + p * 3]a2na3iimag = (a2 - a3) * iimag % moda[i + offset] = (a0 + a1 + a2 + a3) % moda[i + offset + p] = (a0 - a1 + a2na3iimag) * irot % moda[i + offset + p * 2] = (a0 + a1 - a2 - a3) * irot2 % moda[i + offset + p * 3] = (a0 - a1 - a2na3iimag) * irot3 % modirot *= irate3[topbit(~s & -~s)]irot %= modle -= 2def convolute_naive(a,b):res = [0] * (len(a) + len(b) - 1)for i in range(len(a)):for j in range(len(b)):res[i + j] = (res[i + j] + a[i] * b[j] % mod) % modreturn resdef convolute(a,b):s = a[:]t = b[:]n = len(s)m = len(t)if min(n,m) <= 30:return convolute_naive(a,b)le = 1while le < n + m - 1:le *= 2s += [0] * (le - n)t += [0] * (le - m)ntt(s)ntt(t)for i in range(le):s[i] = s[i] * t[i] % modintt(s)s = s[:n + m - 1]return sdef fps_inv(f,deg = -1):if deg == -1:deg = len(f)res = [0] * degres[0] = 1d = 1while d < deg:a = [0] * (d << 1)tmp = min(len(f),d << 1)a[:tmp] = f[:tmp]b = [0] * (d << 1)b[:d] = res[:d]ntt(a)ntt(b)for i in range(d << 1):a[i] = a[i] * b[i] % modintt(a)a[:d] = [0] * dntt(a)for i in range(d << 1):a[i] = a[i] * b[i] % modintt(a)for j in range(d,min(d << 1,deg)):if a[j]:res[j] = mod - a[j]else:res[j] = 0d <<= 1return resdef fps_div(f,g):n,m = len(f),len(g)if n < m:return [],frev_f = f[:]rev_f = rev_f[::-1]rev_g = g[:]rev_g = rev_g[::-1]rev_q = convolute(rev_f,fps_inv(rev_g,n-m+1))[:n-m+1]q = rev_q[:]q = q[::-1]p = convolute(g,q)r = f[:]for i in range(min(len(p),len(r))):r[i] -= p[i]r[i] %= modwhile len(r):if r[-1] != 0:breakr.pop()return q,rdef fps_add(f,g):n = max(len(f),len(g))res = [0] * nfor i in range(len(f)):res[i] = f[i]for i in range(len(g)):res[i] = (res[i] + g[i]) % modreturn resdef fps_diff(f):if len(f) <= 1:return [0]res = []for i in range(1,len(f)):res.append(i * f[i] % mod)return resdef fps_integrate(f):n = len(f)res = [0] * (n + 1)for i in range(n):res[i + 1] = inv[i + 1] * f[i] % modreturn resdef fps_log(f,deg = -1):assert (f[0] == 1)if deg == -1:deg = len(f)res = convolute(fps_diff(f),fps_inv(f,deg))[:deg - 1]res = fps_integrate(res)return resdef fps_exp(f,deg = -1):if deg == -1:deg = len(f)res = [1,0]if len(f) > 1:res[1] = f[1]g = [1]p = []q = [1,1]m = 2while m < deg:y = res + [0]*mntt(y)p = q[:]z = [y[i] * p[i] for i in range(len(p))]intt(z)z[:m >> 1] = [0] * (m >> 1)ntt(z)for i in range(len(p)):z[i] = z[i] * (-p[i]) % modintt(z)g[m >> 1:] = z[m >> 1:]q = g + [0] * mntt(q)tmp = min(len(f),m)x = f[:tmp] + [0] * (m - tmp)x = fps_diff(x)x.append(0)ntt(x)for i in range(len(x)):x[i] = x[i] * y[i] % modintt(x)for i in range(len(res)):if i == 0:continuex[i-1] -= res[i] * i % modx += [0] * mfor i in range(m-1):x[m+i],x[i] = x[i],0ntt(x)for i in range(len(q)):x[i] = x[i] * q[i] % modintt(x)x.pop()x = fps_integrate(x)x[:m] = [0] * mfor i in range(m,min(len(f),m << 1)):x[i] += f[i]ntt(x)for i in range(len(y)):x[i] = x[i] * y[i] % modintt(x)res[m:] = x[m:]m <<= 1return res[:deg]N,K = map(int,input().split())A = list(map(int,input().split()))P = [0 for i in range(K + 1)]for a in A:P[min(a,K)] += 1D = make_divisors(K)M = len(D)dic = {}for i in range(M):dic[D[i]] = iLOG = [[]]g = [1]for i in range(1,K + 1):g.append(fact_inv[i])gg = fps_log(g,K + 1)LOG.append(gg)C = []for d in D:n = K // dQ = [0 for i in range(n + 1)]for i in range(1,K + 1):Q[min(i // d,n)] += P[i]f = [0 for j in range(n + 1)]f[1] = sum(Q) - Q[0]for i in range(1,n):if Q[i] == 0:continuefor j in range(i + 1,n + 1):f[j] = (f[j] + LOG[i][j] * Q[i] % mod) % modf = fps_exp(f)C.append(f[n] * fact[n] % mod)res = 0for k in range(1,K + 1):g = gcd(k,K)d = K // gres += C[dic[d]]res %= modres = res * inv[K] % modprint(res)