結果

問題 No.1321 塗るめた
ユーザー vwxyzvwxyz
提出日時 2023-04-27 02:25:33
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 664 ms / 2,000 ms
コード長 10,333 bytes
コンパイル時間 313 ms
コンパイル使用メモリ 82,232 KB
実行使用メモリ 129,740 KB
最終ジャッジ日時 2024-04-28 01:51:59
合計ジャッジ時間 16,753 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 45 ms
56,896 KB
testcase_01 AC 125 ms
78,404 KB
testcase_02 AC 47 ms
58,008 KB
testcase_03 AC 47 ms
56,720 KB
testcase_04 AC 44 ms
57,112 KB
testcase_05 AC 47 ms
56,760 KB
testcase_06 AC 45 ms
57,452 KB
testcase_07 AC 48 ms
57,884 KB
testcase_08 AC 49 ms
58,120 KB
testcase_09 AC 60 ms
68,648 KB
testcase_10 AC 46 ms
57,240 KB
testcase_11 AC 69 ms
71,564 KB
testcase_12 AC 367 ms
100,508 KB
testcase_13 AC 173 ms
83,656 KB
testcase_14 AC 235 ms
87,940 KB
testcase_15 AC 371 ms
101,020 KB
testcase_16 AC 386 ms
102,476 KB
testcase_17 AC 114 ms
77,992 KB
testcase_18 AC 660 ms
129,692 KB
testcase_19 AC 237 ms
88,812 KB
testcase_20 AC 364 ms
99,984 KB
testcase_21 AC 380 ms
102,808 KB
testcase_22 AC 651 ms
129,144 KB
testcase_23 AC 663 ms
129,088 KB
testcase_24 AC 652 ms
128,108 KB
testcase_25 AC 658 ms
129,580 KB
testcase_26 AC 659 ms
129,460 KB
testcase_27 AC 643 ms
126,880 KB
testcase_28 AC 654 ms
127,104 KB
testcase_29 AC 654 ms
127,172 KB
testcase_30 AC 664 ms
129,740 KB
testcase_31 AC 373 ms
103,108 KB
testcase_32 AC 371 ms
100,344 KB
testcase_33 AC 364 ms
99,784 KB
testcase_34 AC 385 ms
101,928 KB
testcase_35 AC 372 ms
100,348 KB
testcase_36 AC 62 ms
72,976 KB
testcase_37 AC 382 ms
102,908 KB
testcase_38 AC 379 ms
102,916 KB
testcase_39 AC 376 ms
103,672 KB
testcase_40 AC 377 ms
103,032 KB
testcase_41 AC 382 ms
103,160 KB
testcase_42 AC 46 ms
56,496 KB
testcase_43 AC 366 ms
100,604 KB
testcase_44 AC 363 ms
100,048 KB
testcase_45 AC 378 ms
102,316 KB
testcase_46 AC 166 ms
80,868 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque
import math
import sys
readline=sys.stdin.readline

_fft_mod = 998244353
_fft_sum_e = (911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456, 131300601,
              842657263, 730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443, 56250497, 867605899, 0, 0, 0, 0, 0, 0, 0, 0)
_fft_sum_ie = (86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882, 927414960, 354738543,
               109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183, 824071951, 103369235, 0, 0, 0, 0, 0, 0, 0, 0)


def _butterfly(a):
    n = len(a)
    h = (n - 1).bit_length()
    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 % _fft_mod
                a[i + offset] = (l + r) % _fft_mod
                a[i + offset + p] = (l - r) % _fft_mod
            now *= _fft_sum_e[(~s & -~s).bit_length() - 1]
            now %= _fft_mod


def _butterfly_inv(a):
    n = len(a)
    h = (n - 1).bit_length()
    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) % _fft_mod
                a[i + offset + p] = (l - r) * inow % _fft_mod
            inow *= _fft_sum_ie[(~s & -~s).bit_length() - 1]
            inow %= _fft_mod


def _convolution_naive(a, b):
    n = len(a)
    m = len(b)
    ans = [0] * (n + m - 1)
    if n < m:
        for j in range(m):
            for i in range(n):
                ans[i + j] = (ans[i + j] + a[i] * b[j]) % _fft_mod
    else:
        for i in range(n):
            for j in range(m):
                ans[i + j] = (ans[i + j] + a[i] * b[j]) % _fft_mod
    return ans


def _convolution_fft(a, b):
    a = a.copy()
    b = b.copy()
    n = len(a)
    m = len(b)
    z = 1 << (n + m - 2).bit_length()
    a += [0] * (z - n)
    _butterfly(a)
    b += [0] * (z - m)
    _butterfly(b)
    for i in range(z):
        a[i] = a[i] * b[i] % _fft_mod
    _butterfly_inv(a)
    a = a[:n + m - 1]
    iz = pow(z, _fft_mod - 2, _fft_mod)
    for i in range(n + m - 1):
        a[i] = a[i] * iz % _fft_mod
    return a


def _convolution_square(a):
    a = a.copy()
    n = len(a)
    z = 1 << (2 * n - 2).bit_length()
    a += [0] * (z - n)
    _butterfly(a)
    for i in range(z):
        a[i] = a[i] * a[i] % _fft_mod
    _butterfly_inv(a)
    a = a[:2 * n - 1]
    iz = pow(z, _fft_mod - 2, _fft_mod)
    for i in range(2 * n - 1):
        a[i] = a[i] * iz % _fft_mod
    return a


def convolution(a, b):
    """It calculates (+, x) convolution in mod 998244353. 
    Given two arrays a[0], a[1], ..., a[n - 1] and b[0], b[1], ..., b[m - 1], 
    it calculates the array c of length n + m - 1, defined by

    >   c[i] = sum(a[j] * b[i - j] for j in range(i + 1)) % 998244353.

    It returns an empty list if at least one of a and b are empty.

    Complexity
    ----------

    >   O(n log n), where n = len(a) + len(b).
    """
    n = len(a)
    m = len(b)
    if n == 0 or m == 0:
        return []
    if min(n, m) <= 100:
        return _convolution_naive(a, b)
    if a is b:
        return _convolution_square(a)
    return _convolution_fft(a, b)


# Reference: https://opt-cp.com/fps-fast-algorithms/
def inv(a):
    """It calculates the inverse of formal power series in O(n log n) time, where n = len(a).
    """
    n = len(a)
    assert n > 0 and a[0] != 0
    res = [pow(a[0], _fft_mod - 2, _fft_mod)]
    m = 1
    while m < n:
        f = a[:min(n, 2 * m)]
        g = res.copy()
        f += [0] * (2 * m - len(f))
        _butterfly(f)
        g += [0] * (2 * m - len(g))
        _butterfly(g)
        for i in range(2 * m):
            f[i] = f[i] * g[i] % _fft_mod
        _butterfly_inv(f)
        f = f[m:] + [0] * m
        _butterfly(f)
        for i in range(2 * m):
            f[i] = f[i] * g[i] % _fft_mod
        _butterfly_inv(f)
        f = f[:m]
        iz = pow(2 * m, _fft_mod - 2, _fft_mod)
        iz *= -iz
        iz %= _fft_mod
        for i in range(m):
            f[i] = f[i] * iz % _fft_mod
        res.extend(f)
        m *= 2
    res = res[:n]
    return res

    
def integ_inplace(a):
    n = len(a)
    assert n > 0
    if n == 1:
        return []
    a.pop()
    a.insert(0, 0)
    inv = [1, 1]
    for i in range(2, n):
        inv.append(-inv[_fft_mod%i] * (_fft_mod//i) % _fft_mod)
        a[i] = a[i] * inv[i] % _fft_mod


def deriv_inplace(a):
    n = len(a)
    assert n > 0
    for i in range(2, n):
        a[i] = a[i] * i % _fft_mod
    a.pop(0)
    a.append(0)


def log(a):
    a = a.copy()
    n = len(a)
    assert n > 0 and a[0] == 1
    a_inv = inv(a)
    deriv_inplace(a)
    a = convolution(a, a_inv)[:n]
    integ_inplace(a)
    return a
    

def exp(a):
    a = a.copy()
    n = len(a)
    assert n > 0 and a[0] == 0
    g = [1]
    a[0] = 1
    h_drv = a.copy()
    deriv_inplace(h_drv)
    m = 1
    while m < n:
        f_fft = a[:m] + [0] * m
        _butterfly(f_fft)

        if m > 1:
            _f = [f_fft[i] * g_fft[i] % _fft_mod for i in range(m)]
            _butterfly_inv(_f)
            _f = _f[m // 2:] + [0] * (m // 2)
            _butterfly(_f)
            for i in range(m):
                _f[i] = _f[i] * g_fft[i] % _fft_mod
            _butterfly_inv(_f)
            _f = _f[:m//2]
            iz = pow(m, _fft_mod - 2, _fft_mod)
            iz *= -iz
            iz %= _fft_mod
            for i in range(m//2):
                _f[i] = _f[i] * iz % _fft_mod
            g.extend(_f)

        t = a[:m]
        deriv_inplace(t)
        r = h_drv[:m - 1]
        r.append(0)
        _butterfly(r)
        for i in range(m):
            r[i] = r[i] * f_fft[i] % _fft_mod
        _butterfly_inv(r)
        im = pow(-m, _fft_mod - 2, _fft_mod)
        for i in range(m):
            r[i] = r[i] * im % _fft_mod
        for i in range(m):
            t[i] = (t[i] + r[i]) % _fft_mod
        t = [t[-1]] + t[:-1]

        t += [0] * m
        _butterfly(t)
        g_fft = g + [0] * (2 * m - len(g))
        _butterfly(g_fft)
        for i in range(2 * m):
            t[i] = t[i] * g_fft[i] % _fft_mod
        _butterfly_inv(t)
        t = t[:m]
        i2m = pow(2 * m, _fft_mod - 2, _fft_mod)
        for i in range(m):
            t[i] = t[i] * i2m % _fft_mod
    
        v = a[m:min(n, 2 * m)]
        v += [0] * (m - len(v))
        t = [0] * (m - 1) + t + [0]
        integ_inplace(t)
        for i in range(m):
            v[i] = (v[i] - t[m + i]) % _fft_mod

        v += [0] * m
        _butterfly(v)
        for i in range(2 * m):
            v[i] = v[i] * f_fft[i] % _fft_mod
        _butterfly_inv(v)
        v = v[:m]
        i2m = pow(2 * m, _fft_mod - 2, _fft_mod)
        for i in range(m):
            v[i] = v[i] * i2m % _fft_mod
        
        for i in range(min(n - m, m)):
            a[m + i] = v[i]
        
        m *= 2
    return a


def pow_fps(a, k):
    a = a.copy()
    n = len(a)
    l = 0
    while l < len(a) and not a[l]:
        l += 1
    if l * k >= n:
        return [0] * n
    ic = pow(a[l], _fft_mod - 2, _fft_mod)
    pc = pow(a[l], k, _fft_mod)
    a = log([a[i] * ic % _fft_mod for i in range(l, len(a))])
    for i in range(len(a)):
        a[i] = a[i] * k % _fft_mod
    a = exp(a)
    for i in range(len(a)):
        a[i] = a[i] * pc % _fft_mod
    a = [0] * (l * k) + a[:n - l * k]
    return a
def Extended_Euclid(n,m):
    stack=[]
    while m:
        stack.append((n,m))
        n,m=m,n%m
    if n>=0:
        x,y=1,0
    else:
        x,y=-1,0
    for i in range(len(stack)-1,-1,-1):
        n,m=stack[i]
        x,y=y,x-(n//m)*y
    return x,y

class MOD:
    def __init__(self,p,e=None):
        self.p=p
        self.e=e
        if self.e==None:
            mod=self.p
        else:
            mod=self.p**self.e

    def Pow(self,a,n):
        a%=mod
        if n>=0:
            return pow(a,n,mod)
        else:
            assert math.gcd(a,mod)==1
            x=Extended_Euclid(a,mod)[0]
            return pow(x,-n,mod)

    def Build_Fact(self,N):
        assert N>=0
        self.factorial=[1]
        if self.e==None:
            for i in range(1,N+1):
                self.factorial.append(self.factorial[-1]*i%mod)
        else:
            self.cnt=[0]*(N+1)
            for i in range(1,N+1):
                self.cnt[i]=self.cnt[i-1]
                ii=i
                while ii%self.p==0:
                    ii//=self.p
                    self.cnt[i]+=1
                self.factorial.append(self.factorial[-1]*ii%mod)
        self.factorial_inve=[None]*(N+1)
        self.factorial_inve[-1]=self.Pow(self.factorial[-1],-1)
        for i in range(N-1,-1,-1):
            ii=i+1
            while ii%self.p==0:
                ii//=self.p
            self.factorial_inve[i]=(self.factorial_inve[i+1]*ii)%mod

    def Fact(self,N):
        if N<0:
            return 0
        retu=self.factorial[N]
        if self.e!=None and self.cnt[N]:
            retu*=pow(self.p,self.cnt[N],mod)%mod
            retu%=mod
        return retu

    def Fact_Inve(self,N):
        if self.e!=None and self.cnt[N]:
            return None
        return self.factorial_inve[N]

    def Comb(self,N,K,divisible_count=False):
        if K<0 or K>N:
            return 0
        retu=self.factorial[N]*self.factorial_inve[K]%mod*self.factorial_inve[N-K]%mod
        if self.e!=None:
            cnt=self.cnt[N]-self.cnt[N-K]-self.cnt[K]
            if divisible_count:
                return retu,cnt
            else:
                retu*=pow(self.p,cnt,mod)
                retu%=mod
        return retu

N,M,K=map(int,readline().split())
mod=998244353
MD=MOD(mod)
MD.Build_Fact(N)
P=[None]*(N-K+1)
for i in range(N-K+1):
    P[i]=MD.Fact_Inve(i+1)
P=pow_fps(P,K)
ans=0
for n in range(K,N+1):
    ans+=P[n-K]*MD.Pow(M,N-n)%mod*MD.Fact_Inve(N-n)%mod
ans*=MD.Comb(M,K)*MD.Fact(N)%mod
ans%=mod
print(ans)
0