結果
問題 | No.1964 sum = length |
ユーザー |
👑 |
提出日時 | 2022-06-03 21:26:29 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 117 ms / 2,000 ms |
コード長 | 9,172 bytes |
コンパイル時間 | 199 ms |
コンパイル使用メモリ | 82,704 KB |
実行使用メモリ | 76,800 KB |
最終ジャッジ日時 | 2024-09-21 02:26:39 |
合計ジャッジ時間 | 5,533 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
MOD = 998244353class FFT:inv_ = [1]def __init__(self, MOD=998244353):FFT.MOD = MODg = self.primitive_root_constexpr()ig = pow(g, FFT.MOD - 2, FFT.MOD)FFT.W = [pow(g, (FFT.MOD - 1) >> i, FFT.MOD) for i in range(30)]FFT.iW = [pow(ig, (FFT.MOD - 1) >> i, FFT.MOD) for i in range(30)]def primitive_root_constexpr(self):if FFT.MOD == 998244353:return 3elif FFT.MOD == 200003:return 2elif FFT.MOD == 167772161:return 3elif FFT.MOD == 469762049:return 3elif FFT.MOD == 754974721:return 11divs = [0] * 20divs[0] = 2cnt = 1x = (FFT.MOD - 1) // 2while x % 2 == 0:x //= 2i = 3while i * i <= x:if x % i == 0:divs[cnt] = icnt += 1while x % i == 0:x //= ii += 2if x > 1:divs[cnt] = xcnt += 1g = 2while 1:ok = Truefor i in range(cnt):if pow(g, (FFT.MOD - 1) // divs[i], FFT.MOD) == 1:ok = Falsebreakif ok:return gg += 1def fft(self, k, f):for l in range(k, 0, -1):d = 1 << l - 1U = [1]for i in range(d):U.append(U[-1] * FFT.W[l] % FFT.MOD)for i in range(1 << k - l):for j in range(d):s = i * 2 * d + jf[s], f[s + d] = (f[s] + f[s + d]) % FFT.MOD, U[j] * (f[s] - f[s + d]) % FFT.MODdef ifft(self, k, f):for l in range(1, k + 1):d = 1 << l - 1for i in range(1 << k - l):u = 1for j in range(i * 2 * d, (i * 2 + 1) * d):f[j+d] *= uf[j], f[j + d] = (f[j] + f[j + d]) % FFT.MOD, (f[j] - f[j + d]) % FFT.MODu = u * FFT.iW[l] % FFT.MODdef convolve(self, A, B):n0 = len(A) + len(B) - 1k = (n0).bit_length()n = 1 << kA += [0] * (n - len(A))B += [0] * (n - len(B))self.fft(k, A)self.fft(k, B)A = [a * b % FFT.MOD for a, b in zip(A, B)]self.ifft(k, A)inv = pow(n, FFT.MOD - 2, FFT.MOD)A = [a * inv % FFT.MOD for a in A]del A[n0:]return Aclass FPS:fact = [1]invfact = [1]MOD = Nonedef __init__(self, data, MOD=998244353):if FPS.MOD is None:FPS.MOD = MODFPS.fft = FFT(MOD)if type(data) == int:self.f = [data]else:self.f = data[:]def __len__(self):return len(self.f)def __getitem__(self, i):return self.f[i]def __add__(self, other):if len(self) < len(other):other, self = self, otherfor i in range(len(other)):self.f[i] += other[i]if self.f[i] >= FPS.MOD:self.f[i] -= FPS.MODreturn selfdef __iadd__(self, other):return self.__add__(other)def __sub__(self, other):self.f += [0] * (len(other) - len(self))for i in range(len(other)):self.f[i] -= other[i]if self.f[i] < 0:self.f[i] += FPS.MODreturn selfdef __isub__(self, other):return self.__sub__(other)def __mul__(self, other):if type(other) == int:f = [other * x % FPS.MOD for x in self.f]return FPS(f)f = FPS.fft.convolve(self.f[:], other.f[:])return FPS(f)def __imul__(self, other):if type(other) == int:self.f = [other * x % FPS.MOD for x in self.f]return selfself.f = FPS.fft.convolve(self.f, other.f[:])return selfdef inv(self, deg=None):if deg is None:deg = len(self)g = FPS(pow(self[0], FPS.MOD - 2, FPS.MOD))l = 1while l < deg:tmp = g * 2l *= 2tmp2 = FPS(self.f[:l]) * (g * g)g = tmp - tmp2del g.f[l:]del g.f[deg:]return gdef differential(self):return FPS([x * i % FPS.MOD for i, x in enumerate(self.f[1:], 1)])def extend_fact(self, l):l1 = len(FPS.fact)l += 1if l1 <= l:FPS.fact += [0] * (l - l1)FPS.invfact += [0] * (l - l1)for i in range(l1, l):FPS.fact[i] = FPS.fact[i - 1] * i % FPS.MODFPS.invfact[l - 1] = pow(FPS.fact[l - 1], FPS.MOD - 2, FPS.MOD)for i in range(l - 1, l1, -1):FPS.invfact[i - 1] = FPS.invfact[i] * i % FPS.MODdef integral(self):self.extend_fact(len(self))return FPS([0] + [x * (FPS.fact[i] * FPS.invfact[i + 1] % FPS.MOD) % FPS.MOD for i, x in enumerate(self.f)])def log(self, deg=None):if deg is None:deg = len(self)tmp = self.differential() * self.inv(deg=deg)del tmp.f[deg:]tmp = tmp.integral()del tmp.f[deg:]return tmpdef exp(self, deg=None):if deg is None:deg = len(self)g = FPS(1)l = 1while l < deg * 2:l *= 2log = FPS(1) - g.log(deg=l) + FPS(self.f[:l])del log.f[l:]g *= logdel g.f[l:]del g.f[deg:]return gdef __pow__(self, k, deg=None):if deg is None:deg = len(self)i = 0p = Nonefor i in range(deg):if self[i] != 0:a = self[i]p = ibreakif p is None:if deg is not None:return FPS([0] * deg)else:return FPS(0)elif deg is not None and p * k >= deg:return FPS([0] * deg)inv = pow(a, FPS.MOD - 2, FPS.MOD)tmp = FPS([x * inv % FPS.MOD for x in self.f[p:]])tmp = tmp.log(deg=deg)if deg is not None:del tmp.f[deg:]tmp *= ktmp = tmp.exp(deg=deg)tmp = [0] * (p * k) + tmp.f[:deg - p * k]times = pow(a, k, FPS.MOD)return FPS([x * times % FPS.MOD for x in tmp])def __ipow__(self, k):return self.__pow__(k)def cipolla(self, a):if FPS.MOD == 2:return aelif a == 0:return 0elif pow(a, (FPS.MOD - 1) // 2, FPS.MOD) != 1:return -1b = 0while pow((b * b + FPS.MOD - a) % FPS.MOD, (FPS.MOD - 1) // 2, FPS.MOD) == 1:b += 1base = b * b + FPS.MOD - adef multi(a0, b0, a1, b1):return (a0 * a1 + (b0 * b1 % FPS.MOD) * base) % FPS.MOD, (a0 * b1 + b0 * a1) % FPS.MODdef pow_(a, b, n):if n == 0:return 1, 0a_, b_ = pow_(*multi(a, b, a, b), n // 2)if n % 2 == 1:a_, b_ = multi(a_, b_, a, b)return a_, b_return pow_(b, 1, (FPS.MOD + 1) // 2)[0]def sqrt(self, deg=None):if deg is None:deg = len(self)if len(self) == 0:return FPS([0] * deg)if self[0] == 0:for i in range(1, len(self)):if self[i] != 0:if i & 1:return FPS([])if deg <= i // 2:breakret = FPS(self.f[i:]).sqrt(deg - i // 2)if len(ret) == 0:return FPS([])ret.f = [0] * (i // 2) + ret.fif len(ret) < deg:ret.f += [0] * (deg - len(ret))return retreturn FPS([0] * deg)sq = self.cipolla(self[0])if sq == -1:return FPS([])inv2 = (FPS.MOD + 1) // 2g = FPS([sq])l = 1while l < deg:l *= 2tmp = FPS(self.f[:l]) * g.inv(deg=l)g += tmpg *= inv2del g.f[deg:]return gdef taylorshift(self, a):deg = len(self)f = self.f[:]self.extend_fact(deg)for i in range(deg):f[i] *= FPS.fact[i]f[i] %= FPS.MODf = f[::-1]g = [0] * degg[0] = 1for i in range(1, deg):g[i] = (g[i - 1] * a % FPS.MOD) * (FPS.fact[i - 1] * FPS.invfact[i] % FPS.MOD) % FPS.MODf = FPS.fft.convolve(f, g)del f[deg:]f = f[::-1]for i in range(deg):f[i] *= FPS.invfact[i]f[i] %= FPS.MODreturn FPS(f)n = int(input())f = [0] * (n + 10)for i in range(1, n + 3):l = len(str(i))f[i - l] += 1F = FPS(f)F **= nprint(F.f[n-1])