結果

問題 No.1392 Don't be together
ユーザー chineristACchineristAC
提出日時 2020-09-01 15:05:57
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 1,943 ms / 2,000 ms
コード長 3,853 bytes
コンパイル時間 185 ms
コンパイル使用メモリ 13,312 KB
実行使用メモリ 79,376 KB
最終ジャッジ日時 2024-05-01 01:33:29
合計ジャッジ時間 35,824 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,011 ms
78,740 KB
testcase_01 AC 1,052 ms
78,996 KB
testcase_02 AC 1,007 ms
78,872 KB
testcase_03 AC 990 ms
78,868 KB
testcase_04 AC 1,010 ms
78,748 KB
testcase_05 AC 1,012 ms
79,376 KB
testcase_06 AC 1,943 ms
78,728 KB
testcase_07 AC 1,103 ms
78,744 KB
testcase_08 AC 1,275 ms
78,916 KB
testcase_09 AC 1,769 ms
78,744 KB
testcase_10 AC 1,079 ms
78,564 KB
testcase_11 AC 1,129 ms
78,788 KB
testcase_12 AC 1,086 ms
78,736 KB
testcase_13 AC 1,072 ms
78,868 KB
testcase_14 AC 1,089 ms
78,688 KB
testcase_15 AC 1,107 ms
78,684 KB
testcase_16 AC 1,083 ms
78,880 KB
testcase_17 AC 1,090 ms
78,880 KB
testcase_18 AC 1,114 ms
78,740 KB
testcase_19 AC 1,085 ms
78,732 KB
testcase_20 AC 1,061 ms
78,744 KB
testcase_21 AC 1,042 ms
78,868 KB
testcase_22 AC 1,086 ms
78,844 KB
testcase_23 AC 1,089 ms
78,792 KB
testcase_24 AC 1,079 ms
78,736 KB
testcase_25 AC 1,078 ms
78,800 KB
testcase_26 AC 1,087 ms
79,260 KB
testcase_27 AC 1,075 ms
78,920 KB
testcase_28 AC 1,056 ms
78,740 KB
testcase_29 AC 1,067 ms
78,784 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

def cmb(n, r, mod):#コンビネーションの高速計算　
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 998244353
N = 2*10**5
g1 = [1]*(N+1) # 元テーブル
g2 = [1]*(N+1) #逆元テーブル
inverse = [1]*(N+1) #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1[i]=( ( g1[i-1] * i ) % mod )
    inverse[i]=( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2[i]=( (g2[i-1] * inverse[i]) % mod )
inverse[0]=0

mod = 998244353

import numpy as np

N = 2**18
inv = [1]*(N+1) #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    inv[i]=( ( -inv[mod % i] * (mod//i) ) % mod )
inv[0]=0

inv = np.array(inv,np.int64)

def convolve(f,g,limit):
    fft_len =1
    while 2*fft_len<len(f)+len(g)-1:
        fft_len *= 2
    fft_len *=2
    Ff = np.fft.rfft(f,fft_len)
    Fg = np.fft.rfft(g,fft_len)

    Fh = Ff * Fg

    h=np.fft.irfft(Fh,fft_len)

    h= np.rint(h).astype(np.int64)

    return h[:min(len(f)+len(g)-1,limit)]

def convolve2(f,g,limit,p=998244353):

    f1,f2=np.divmod(f,1<<15)
    g1,g2=np.divmod(g,1<<15)

    a = convolve(f1,g1,limit)%p
    c = convolve(f2,g2,limit)%p
    b = (convolve(f1+f2,g1+g2,limit)-(a+c))%p

    h = (a<<30) + (b<<15) +c
    return h[:limit] % p

def inverse(f,limit):
    g = np.array([pow(int(f[0]),mod-2,mod)],np.int64)
    f = list(f)
    n = (len(f)-1).bit_length()
    F = f + [0]*(2**n-len(f))

    f=np.array(F,np.int64)

    for i in range(1,n+1):
        h = convolve2(g,f[:2**i],2**i)
        h = (-h) % mod
        h[0] = (h[0] + 2) %mod
        g = convolve2(g,h,2**i)
    return g[:limit]

def integral(f,limit):
    F = np.zeros(len(f),np.int64)
    F[1:] = f[:len(f)-1] * inv[1:len(f)]
    return (F % mod)[:limit]

def diff(f,limit):
    arange = np.array([i for i in range(len(f))],np.int64)
    res = (f * arange) % mod
    res = np.resize(res[1:],limit)
    res[-1] = 0
    return res[:limit]

def log(f,limit):
    res = convolve2(diff(f,limit),inverse(f,limit),limit)
    return integral(res,limit)

def exp(f,limit):
    l = len(f)
    L = 1<<((l-1).bit_length())
    n = L.bit_length()-1
    f = np.resize(f,L)
    f[L:] = 0

    res = np.array([1],np.int64)
    for i in range(1,n+1):
        res = np.resize(res,2**i)
        res[2**(i-1):] = 0
        g = log(res,2**i)
        h = (f[:2**i]-g[:2**i]) % mod
        h[0] = (h[0] + 1) % mod
        res = convolve2(res,h,2**i)
    return res[:limit]

def pow_poly(f,k,limit):
    l = len(f)
    L = 1<<((l-1).bit_length())
    n = L.bit_length()-1
    f = np.resize(f,L)
    f[L:] = 0

    g = (k * log(f,limit)) % mod
    h = exp(g,limit)

    return h[:limit]

def main():
    N,M = map(int,input().split())
    P = list(map(int,input().split()))

    P = [P[i]-1 for i in range(N)]
    cycle = []
    used = [False]*N
    for i in range(N):
        if not used[i]:
            used[i] = True
            c = 1
            pos = i
            while not used[P[pos]]:
                pos = P[pos]
                used[pos] = True
                c += 1
            cycle.append(c)

    n = len(cycle)

    binom_poly = np.array([1],np.int64)
    for i in range(n):
        c = [cmb(cycle[i],j,mod)*pow(-1,j,mod) for j in range(1,cycle[i]+1)]
        c[0] = (c[0] + 1) % mod
        c = np.array(c,np.int64)
        c %= mod
        binom_poly = convolve2(binom_poly,c,len(binom_poly)+cycle[i]-1)

    g = [g2[i+1] for i in range(N+1)]
    g = np.array(g,np.int64)
    res = pow_poly(g,M,N+1)
    res = (res * g2[M]) % mod
    res = list(res)
    Res = [0 for i in range(N+1)]
    for i in range(N-M+1):
        Res[i+M] = (res[i] * g1[i+M]) % mod
    res = Res

    ans = 0
    for j in range(N-n+1):
        ans += res[n+j] * binom_poly[j]
        ans %= mod
    print((ans*(-1)**N)%mod)

if __name__=="__main__":
    main()
0