""" Mod はグローバル変数からの指定とする. """ """ 積 """ def product_modulo(*X): y=1 for x in X: y=(x*y)%Mod return y """ 階乗 """ def Factor(N): """ 0!, 1!, ..., N! (mod Mod) を出力する. N: int """ f=[1]*(N+1) for k in range(1,N+1): f[k]=(k*f[k-1])%Mod return f def Factor_with_inverse(N): """ 0!, 1!, ..., N!, (0!)^-1, (1!)^-1, ..., (N!)^-1 を出力する. N: int """ f = Factor(N) g = [0]*(N+1) N = min(N, Mod-1) g[N] = pow(f[N], Mod - 2, Mod) for k in range(N-1,-1,-1): g[k] = ((k+1) * g[k+1]) % Mod return f, g def Double_Factor(N): """ 0!!, 1!!, ..., N!! (mod Mod) を出力する. N: int """ f=[1]*(N+1) for i in range(2,N+1): f[i]=i*f[i-2]%Mod return f def Modular_Inverse(N): """ 1^(-1), 2^(-1), ..., N^(-1) (mod Mod) を出力する. [Input] N:int [Output] [-1, 1^(-1), 2^(-1), ..., N^(-1)] (第 0 要素に注意!!) """ inv=[1]*(N+1); inv[0]=-1 for k in range(2, N+1): q,r=divmod(Mod,k) inv[k]=(-q*inv[r])%Mod return inv """ 組み合わせの数 Factor_with_inverse で fact, fact_inv を既に求めていることが前提 (グローバル変数) """ def nCr(n,r): """ nCr (1,2,...,n から相異なる r 個の整数を選ぶ方法) を求める. n,r: int """ if 0<=r<=n: return fact[n]*(fact_inv[r]*fact_inv[n-r]%Mod)%Mod else: return 0 def nPr(n,r): """ nPr (1,2,...,n から相異なる r 個の整数を選び, 並べる方法) を求める. n,r: int """ if 0<=r<=n: return (fact[n]*fact_inv[n-r])%Mod else: return 0 def nHr(n,r): """ nHr (1,2,...,n から重複を許して r 個の整数を選ぶ方法) を求める. n,r: int ※ fact, fact_inv は第 n+r-1 項まで必要 """ if n==r==0: return 1 else: return nCr(n+r-1,r) def Multinomial_Coefficient(*K): """ K=[k_0,...,k_{r-1}] に対して, k_0, ..., k_{r-1} に対する多項係数を求める. k_i: int """ N=0 g_inv=1 for k in K: N+=k g_inv*=fact_inv[k]; g_inv%=Mod return (fact[N]*g_inv)%Mod def Binomial_Coefficient_Modulo_List(n: int): """ n を固定し, r=0,1,...,n としたときの nCr (mod Mod) のリストを出力する. n: int [出力] [nC0 , nC1 ,..., nCn] """ L=[1]*(n+1) inv=Modular_Inverse(n+1) for r in range(1, n+1): L[r]=((n+1-r)*inv[r]%Mod)*L[r-1]%Mod return L def Pascal_Triangle(N: int, mode=False): """ 0<=n<=N, 0<=r<=n の全てに対して nCr (mod M) のリストを出力する. N: int [出力] [[0C0], [1C0, 1C1], ... , [nC0, ... , nCn], ..., [NC0, ..., NCN]] """ if mode: L=[[0]*(N+1) for _ in range(N+1)] L[0][0]=1 for n in range(1,N+1): Ln=L[n]; Lnn=L[n-1] Ln[0]=1 for r in range(1,N+1): Ln[r]=(Lnn[r]+Lnn[r-1])%Mod return L else: X=[1] L=[[1]] for n in range(N): Y=[1] for k in range(1, n+1): Y.append((X[k]+X[k-1])%Mod) Y.append(1) X=Y L.append(Y) return L def Lucas_Combination(n, r): """ Lucas の定理を用いて nCr (mod Mod) を求める. """ X=1 while n or r: ni=n%Mod; ri=r%Mod n//=Mod; r//=Mod if ni=q*q: e=0 while v%q==0: e+=1 v//=q if e>0: fac.append(q) q+=1 if v>1: fac.append(v) g=2 while g>rank2, Mod) iroot[-1]=pow(root[-1], -1, Mod) for i in range(rank2)[::-1]: root[i]=root[i+1]*root[i+1]%Mod iroot[i]=iroot[i+1]*iroot[i+1]%Mod prod=iprod=1 for i in range(rank2-1): rate2[i]=root[i+2]*prod%Mod irate2[i]=iroot[i+2]*prod%Mod prod*=iroot[i+2]; prod%=Mod iprod*=root[i+2]; iprod%=Mod prod=iprod = 1 for i in range(rank2-2): rate3[i]=root[i + 3]*prod%Mod irate3[i]=iroot[i + 3]*iprod%Mod prod*=iroot[i + 3]; prod%=Mod iprod*=root[i + 3]; iprod%=Mod self.root=root; self.iroot=iroot self.rate2=rate2; self.irate2=irate2 self.rate3=rate3; self.irate3=irate3 def Add(self, A, B): """ 必要ならば末尾に元を追加して, [A[i]+B[i]] を求める. """ if type(A)==int: A=[A] if type(B)==int: B=[B] m=min(len(A), len(B)) C=[(A[i]+B[i])%Mod for i in range(m)] C.extend(A[m:]) C.extend(B[m:]) return C def Sub(self, A, B): """ 必要ならば末尾に元を追加して, [A[i]-B[i]] を求める. """ if type(A)==int: A=[A] if type(B)==int: B=[B] m=min(len(A), len(B)) C=[0]*m C=[(A[i]-B[i])%Mod for i in range(m)] C.extend(A[m:]) C.extend([-b%Mod for b in B[m:]]) return C def Times(self,A, k): """ [k*A[i]] を求める. """ return [k*a%Mod for a in A] #参考元 https://judge.yosupo.jp/submission/72676 def NTT(self, A): """ A に Mod を法とする数論変換を施す ※ Mod はグローバル変数から指定 References: https://github.com/atcoder/ac-library/blob/master/atcoder/convolution.hpp https://judge.yosupo.jp/submission/72676 """ N=len(A) H=(N-1).bit_length() l=0 I=self.root[2] rate2=self.rate2; rate3=self.rate3 while l=2: i=Q.popleft(); j=Q.popleft() A[i]=self.Convolution(A[i], A[j]) A[j]=None Q.append(i) i=Q.popleft() return A[i] def Inverse(self, F, length=None): if length==None: M=len(F) else: M=length if M<=0: return [] if self.is_sparse(F): """ 愚直に漸化式を用いて求める. 計算量: F にある係数が非零の項の個数を K, 求める最大次数を N として, O(NK) 時間 """ d,f=self.coefficients_list(F) G=[0]*M alpha=pow(F[0], -1, Mod) G[0]=alpha for i in range(1, M): for j in range(1, len(d)): if d[j]<=i: G[i]+=f[j]*G[i-d[j]]%Mod else: break G[i]%=Mod G[i]=(-alpha*G[i])%Mod del G[M:] else: """ FFTの理論を応用して求める. 計算量: 求めたい項の個数をNとして, O(N log N) Reference: https://judge.yosupo.jp/submission/42413 """ N=len(F) r=pow(F[0], -1, Mod) m=1 G=[r] while m