結果

問題 No.1964 sum = length
ユーザー 👑 rin204rin204
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 69 ms
65,920 KB
testcase_01 AC 68 ms
66,432 KB
testcase_02 AC 79 ms
70,912 KB
testcase_03 AC 67 ms
66,048 KB
testcase_04 AC 67 ms
66,560 KB
testcase_05 AC 71 ms
66,048 KB
testcase_06 AC 67 ms
65,792 KB
testcase_07 AC 66 ms
66,048 KB
testcase_08 AC 69 ms
66,048 KB
testcase_09 AC 83 ms
71,164 KB
testcase_10 AC 92 ms
70,656 KB
testcase_11 AC 77 ms
70,784 KB
testcase_12 AC 76 ms
73,856 KB
testcase_13 AC 83 ms
76,416 KB
testcase_14 AC 85 ms
76,624 KB
testcase_15 AC 84 ms
76,524 KB
testcase_16 AC 70 ms
70,912 KB
testcase_17 AC 75 ms
73,472 KB
testcase_18 AC 73 ms
73,856 KB
testcase_19 AC 73 ms
73,764 KB
testcase_20 AC 75 ms
73,568 KB
testcase_21 AC 76 ms
71,168 KB
testcase_22 AC 107 ms
76,544 KB
testcase_23 AC 106 ms
76,544 KB
testcase_24 AC 104 ms
76,160 KB
testcase_25 AC 104 ms
76,800 KB
testcase_26 AC 106 ms
76,544 KB
testcase_27 AC 104 ms
76,544 KB
testcase_28 AC 105 ms
76,544 KB
testcase_29 AC 117 ms
76,544 KB
testcase_30 AC 107 ms
76,800 KB
testcase_31 AC 107 ms
76,672 KB
testcase_32 AC 104 ms
76,544 KB
testcase_33 AC 100 ms
76,588 KB
testcase_34 AC 109 ms
76,628 KB
testcase_35 AC 99 ms
76,032 KB
testcase_36 AC 114 ms
76,288 KB
testcase_37 AC 113 ms
76,672 KB
testcase_38 AC 96 ms
76,160 KB
testcase_39 AC 94 ms
76,416 KB
testcase_40 AC 94 ms
76,416 KB
testcase_41 AC 94 ms
76,544 KB
testcase_42 AC 92 ms
76,596 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353
class FFT:
    inv_ = [1]

    def __init__(self, MOD=998244353):
        FFT.MOD = MOD
        g = 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 3
        elif FFT.MOD == 200003:
            return 2
        elif FFT.MOD == 167772161:
            return 3
        elif FFT.MOD == 469762049:
            return 3
        elif FFT.MOD == 754974721:
            return 11
        divs = [0] * 20
        divs[0] = 2
        cnt = 1
        x = (FFT.MOD - 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, (FFT.MOD - 1) // divs[i], FFT.MOD) == 1:
                    ok = False
                    break
            if ok:
                return g
            g += 1

    def fft(self, k, f):
        for l in range(k, 0, -1):
            d = 1 << l - 1
            U = [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 + j
                    f[s], f[s + d] = (f[s] + f[s + d]) % FFT.MOD, U[j] * (f[s] - f[s + d]) % FFT.MOD

    def ifft(self, k, f):
        for l in range(1, k + 1):
            d = 1 << l - 1
            for i in range(1 << k - l):
                u = 1
                for j in range(i * 2 * d, (i * 2 + 1) * d):
                    f[j+d] *= u
                    f[j], f[j + d] = (f[j] + f[j + d]) % FFT.MOD, (f[j] - f[j + d]) % FFT.MOD
                    u = u * FFT.iW[l] % FFT.MOD

    def convolve(self, A, B):
        n0 = len(A) + len(B) - 1
        k = (n0).bit_length()
        n = 1 << k
        A += [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 A

class FPS:
    fact = [1]
    invfact = [1]
    MOD = None
    def __init__(self, data, MOD=998244353):
        if FPS.MOD is None:
            FPS.MOD = MOD
            FPS.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, other
        for i in range(len(other)):
            self.f[i] += other[i]
            if self.f[i] >= FPS.MOD:
                self.f[i] -= FPS.MOD
        return self
    
    def __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.MOD
        return self

    def __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 self
        self.f = FPS.fft.convolve(self.f, other.f[:])
        return self

    def inv(self, deg=None):
        if deg is None:
            deg = len(self)
        g = FPS(pow(self[0], FPS.MOD - 2, FPS.MOD))
        l = 1
        while l < deg:
            tmp = g * 2
            l *= 2
            tmp2 = FPS(self.f[:l]) * (g * g)
            g = tmp - tmp2
            del g.f[l:]
        del g.f[deg:]
        return g

    def 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 += 1
        if 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.MOD
            FPS.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.MOD

    def 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 tmp

    def exp(self, deg=None):
        if deg is None:
            deg = len(self)
        g = FPS(1)
        l = 1
        while l < deg * 2:
            l *= 2
            log = FPS(1) - g.log(deg=l) + FPS(self.f[:l])
            del log.f[l:]
            g *= log
            del g.f[l:]
        del g.f[deg:]
        return g

    def __pow__(self, k, deg=None):
        if deg is None:
            deg = len(self)
        i = 0
        p = None
        for i in range(deg):
            if self[i] != 0:
                a = self[i]
                p = i
                break
        if 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 *= k        
        tmp = 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 a
        elif a == 0:
            return 0
        elif pow(a, (FPS.MOD - 1) // 2, FPS.MOD) != 1:
            return -1
        b = 0
        while pow((b * b + FPS.MOD - a) % FPS.MOD, (FPS.MOD - 1) // 2, FPS.MOD) == 1:
            b += 1
        
        base = b * b + FPS.MOD - a
        
        def multi(a0, b0, a1, b1):
            return (a0 * a1 + (b0 * b1 % FPS.MOD) * base) % FPS.MOD, (a0 * b1 + b0 * a1) % FPS.MOD

        def pow_(a, b, n):
            if n == 0:
                return 1, 0
            a_, 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:
                        break
                    ret = FPS(self.f[i:]).sqrt(deg - i // 2)
                    if len(ret) == 0:
                        return FPS([])
                    ret.f = [0] * (i // 2) + ret.f
                    if len(ret) < deg:
                        ret.f += [0] * (deg - len(ret))
                    return ret
            return FPS([0] * deg)
        
        sq = self.cipolla(self[0])
        if sq == -1:
            return FPS([])
        inv2 = (FPS.MOD + 1) // 2
        g = FPS([sq])
        l = 1
        while l < deg:
            l *= 2
            tmp = FPS(self.f[:l]) * g.inv(deg=l)
            g += tmp
            g *= inv2

        del g.f[deg:]
        return g

    def 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.MOD
        f = f[::-1]
        g = [0] * deg
        g[0] = 1
        for i in range(1, deg):
            g[i] = (g[i - 1] * a % FPS.MOD) * (FPS.fact[i - 1] * FPS.invfact[i] % FPS.MOD) % FPS.MOD
        f = FPS.fft.convolve(f, g)
        del f[deg:]
        f = f[::-1]
        for i in range(deg):
            f[i] *= FPS.invfact[i]
            f[i] %= FPS.MOD
        return FPS(f)

n = int(input())
f = [0] * (n + 10)
for i in range(1, n + 3):
    l = len(str(i))
    f[i - l] += 1
F = FPS(f)
F **= n
print(F.f[n-1])
0