mod=924844033 root=pow(5,441,mod) rootinv=pow(root,mod-2,mod) bbeki=[0]*22 bbeki2=[0]*22 beki_dic=dict() this=1 for i in range(22): beki_dic[this]=i this*=2 def beki_mae(): x=root beki=1 for i in range(21,-1,-1): bbeki[i]=x x=x**2 x%=mod x=rootinv beki=1 for i in range(21,-1,-1): bbeki2[i]=x x=x**2 x%=mod beki_mae() def rev(i,k): ans=0 s=bin(i)[2:] for i in range(len(s)): if s[len(s)-1-i]=="1": ans+=2**(k-1-i) return ans def NTT_len(a):#a<=2^Nを満たす最小のNを返す k=1 b=0 for i in range(100): if k>=a: break else: k*=2 b+=1 return b def NTT_change0(A,k):#長さ2^kにする N=len(A) A=A+[0]*(2**k-N) NTT_change(A) return A def NTT_change(A):#Aをstart<=k1: x=bbeki[beki_dic[le]] for st in range(N//le): this=1 for i in range(le//2): l=A[st*le+i] r=A[st*le+i+le//2] A[st*le+i]=(l+r)%mod A[st*le+i+le//2]=((l-r)*this)%mod this*=x this%=mod le//=2 def NTT_invchange0(A,k):#長さ2^kにする N=len(A) A=A+[0]*(2**k-N) NTT_invchange(A) return A def NTT_invchange(A):#Aをstart<=k