結果
| 問題 | No.1195 数え上げを愛したい（文字列編） |
| ユーザー |
 37zigen
|
| 提出日時 | 2020-08-23 06:37:57 |
| 言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 1,032 bytes |
| コンパイル時間 | 164 ms |
| コンパイル使用メモリ | 12,672 KB |
| 実行使用メモリ | 170,812 KB |
| 最終ジャッジ日時 | 2024-10-15 16:44:52 |
| 合計ジャッジ時間 | 8,761 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
ソースコード
import numpy as np
MOD=998244353
def convolve(f,g):
fft=np.fft.rfft
ifft=np.fft.irfft
Lf=len(f)
Lg=len(g)
L=Lf+Lg-1
fft_len=1<<L.bit_length()
fl=f&(1<<15)-1
gl=g&(1<<15)-1
fh=f>>15
gh=g>>15
def conv(f,g):
return ifft(fft(f,fft_len)*fft(g,fft_len))[:L]
# (ax+b)(cx+d)=acxx+(ad+bc)x+bd=acxx+{(a+b)(c+d)-(ac+bd)}x+bd
x=conv(fl,gl)%MOD
y=conv(fl+fh,gl+gh)%MOD
z=conv(fh,gh)%MOD
a,b,c=map(lambda x : (x+.5).astype(np.int64) ,[x,y,z])
return (a+((b-a-c)<<15)+(c<<30))%MOD
fac=[1,1]
inv=[1,1]
ifac=[1,1]
for i in range(2,3*(10**5)):
fac.append(fac[-1]*i%MOD)
inv.append(MOD-MOD//i*inv[MOD%i]%MOD)
ifac.append(ifac[-1]*inv[i]%MOD)
S=input()
cnt=[0]*27
for s in S:
cnt[ord(s)-ord('a')]+=1
poly=np.array([1],np.int64)
for i in range(27):
f=np.array([0]*(len(S)+1),np.int64)
for j in range(cnt[i]+1):
f[j]=ifac[j]
poly=convolve(poly,f)[:len(S)+1]
ans=0
for i in range(1,len(S)+1):
ans=(ans+poly[i]*fac[i])%MOD
print(ans)