結果
| 問題 |
No.2097 AND^k
|
| コンテスト | |
| ユーザー |
 taiga0629kyopro
|
| 提出日時 | 2022-09-20 10:28:29 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,830 bytes |
| コンパイル時間 | 178 ms |
| コンパイル使用メモリ | 82,176 KB |
| 実行使用メモリ | 273,688 KB |
| 最終ジャッジ日時 | 2024-12-22 04:22:53 |
| 合計ジャッジ時間 | 105,062 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 6 TLE * 17 |
ソースコード
mod=998244353
#############################
#############
cnb_max=3*10**5
#############
kai=[1]*(cnb_max+1)
rkai=[1]*(cnb_max+1)
for i in range(cnb_max):
kai[i+1]=kai[i]*(i+1)%mod
rkai[cnb_max]=pow(kai[cnb_max],mod-2,mod)
for i in range(cnb_max):
rkai[cnb_max-1-i]=rkai[cnb_max-i]*(cnb_max-i)%mod
def cnb(x,y):
if y>x:
return 0
if x<0:return 0
if y<0:return 0
return (kai[x]*rkai[y]%mod)*rkai[x-y]%mod
def inv(n):
return kai[n-1]*rkai[n]%mod
##################################
class FFT():
def primitive_root_constexpr(self,m):
if m==2:return 1
if m==167772161:return 3
if m==469762049:return 3
if m==754974721:return 11
if m==998244353:return 3
divs=[0]*20
divs[0]=2
cnt=1
x=(m-1)//2
while(x%2==0):x//=2
i=3
while(i*i<=x):
if (x%i==0):
divs[cnt]=i
cnt+=1
while(x%i==0):
x//=i
i+=2
if x>1:
divs[cnt]=x
cnt+=1
g=2
while(1):
ok=True
for i in range(cnt):
if pow(g,(m-1)//divs[i],m)==1:
ok=False
break
if ok:
return g
g+=1
def bsf(self,x):
res=0
while(x%2==0):
res+=1
x//=2
return res
butterfly_first=True
butterfly_inv_first=True
sum_e=[0]*30
sum_ie=[0]*30
def __init__(self,MOD):
self.mod=MOD
self.g=self.primitive_root_constexpr(self.mod)
def butterfly(self,a):
n=len(a)
h=(n-1).bit_length()
if self.butterfly_first:
self.butterfly_first=False
es=[0]*30
ies=[0]*30
cnt2=self.bsf(self.mod-1)
e=pow(self.g,(self.mod-1)>>cnt2,self.mod)
ie=pow(e,self.mod-2,self.mod)
for i in range(cnt2,1,-1):
es[i-2]=e
ies[i-2]=ie
e=(e*e)%self.mod
ie=(ie*ie)%self.mod
now=1
for i in range(cnt2-2):
self.sum_e[i]=((es[i]*now)%self.mod)
now*=ies[i]
now%=self.mod
for ph in range(1,h+1):
w=1<<(ph-1)
p=1<<(h-ph)
now=1
for s in range(w):
offset=s<<(h-ph+1)
for i in range(p):
l=a[i+offset]
r=a[i+offset+p]*now
r%=self.mod
a[i+offset]=l+r
a[i+offset]%=self.mod
a[i+offset+p]=l-r
a[i+offset+p]%=self.mod
now*=self.sum_e[(~s & -~s).bit_length()-1]
now%=self.mod
def butterfly_inv(self,a):
n=len(a)
h=(n-1).bit_length()
if self.butterfly_inv_first:
self.butterfly_inv_first=False
es=[0]*30
ies=[0]*30
cnt2=self.bsf(self.mod-1)
e=pow(self.g,(self.mod-1)>>cnt2,self.mod)
ie=pow(e,self.mod-2,self.mod)
for i in range(cnt2,1,-1):
es[i-2]=e
ies[i-2]=ie
e=(e*e)%self.mod
ie=(ie*ie)%self.mod
now=1
for i in range(cnt2-2):
self.sum_ie[i]=((ies[i]*now)%self.mod)
now*=es[i]
now%=self.mod
for ph in range(h,0,-1):
w=1<<(ph-1)
p=1<<(h-ph)
inow=1
for s in range(w):
offset=s<<(h-ph+1)
for i in range(p):
l=a[i+offset]
r=a[i+offset+p]
a[i+offset]=l+r
a[i+offset]%=self.mod
a[i+offset+p]=(l-r)*inow
a[i+offset+p]%=self.mod
inow*=self.sum_ie[(~s & -~s).bit_length()-1]
inow%=self.mod
def convolution(self,a,b):
n=len(a);m=len(b)
if not(a) or not(b):
return []
if min(n,m)<=40:
if n<m:
n,m=m,n
a,b=b,a
res=[0]*(n+m-1)
for i in range(n):
for j in range(m):
res[i+j]+=a[i]*b[j]
res[i+j]%=self.mod
return res
z=1<<((n+m-2).bit_length())
a=a+[0]*(z-n)
b=b+[0]*(z-m)
self.butterfly(a)
self.butterfly(b)
c=[0]*z
for i in range(z):
c[i]=(a[i]*b[i])%self.mod
self.butterfly_inv(c)
iz=pow(z,self.mod-2,self.mod)
for i in range(n+m-1):
c[i]=(c[i]*iz)%self.mod
return c[:n+m-1]
fft=FFT(mod)
def naive(n,m,l):
dp=[0]*(2**m)
dp[2**m-1]=1
for i in range(n):
newdp=[0]*(2**m)
for j in range(2**m):
for ai in range(2**m):
dp[j]%=mod
newdp[j&ai]+=dp[j]
dp=newdp[:]
ans=[0]
for k in range(1,l+1):
res=0
for j in range(2**m):
res+=pow(j,k,mod)*dp[j]
res%=mod
ans.append(res%mod)
return ans
def sol1(n,m,l):
fx=[0]*(l+1)
fx[0]=1
invn2=pow(2,n*(mod-2),mod)
for i in range(m):
gx=[0]*(l+1)
gx[0]=1
i2=pow(2,i,mod)
nod=i2
for a in range(1,l+1):
gx[a]=nod*rkai[a]%mod
gx[a]*=invn2
gx[a]%=mod
nod=nod*i2%mod
fx=fft.convolution(fx,gx)[:l+1]
ans=[0]
for k in range(1,l+1):
res=pow(2,n*m,mod)*kai[k]%mod
res*=fx[k]
ans.append(res%mod)
return ans
n,m,l=map(int,input().split())
ans=sol1(n,m,l)
for k in range(1,l+1):print(ans[k])