結果

問題 No.2381 Gift Exchange Party
ユーザー steinnsteinn
提出日時 2023-07-17 22:25:45
言語 Julia
(1.10.2)
結果
TLE  
実行時間 -
コード長 1,893 bytes
コンパイル時間 139 ms
コンパイル使用メモリ 6,944 KB
実行使用メモリ 961,272 KB
最終ジャッジ日時 2024-04-09 14:29:14
合計ジャッジ時間 5,483 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 425 ms
252,568 KB
testcase_01 AC 424 ms
253,108 KB
testcase_02 TLE -
testcase_03 MLE -
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 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

parseInt() = parse.(Int64, readline()::String |> split)::Vector{Int64}
parseInt2() = parse.(Int64, readline()::String |> collect)::Vector{Int64}
parseInt3() = parse(Int64, readline()::String)::Int64

module Modulo
mod = 998244353

export Mint, pow
mutable struct Mint
    m::Int64
    Mint(x) = x ≥ 0 ? new(x % mod) : new((mod - (-x) % mod) % mod)
end

function Base.:+(x::Mint, y::Mint)
    return Mint(+(x.m, y.m))
end

function Base.:-(x::Mint, y::Mint)
    return Mint(-(x.m, y.m))
end

function Base.:*(x::Mint, y::Mint)
    return Mint(*(x.m, y.m))
end

function inverse(x::Mint)
    a = x.m
    b = mod
    u = 1
    v = 0
    while b > 0
        t = a ÷ b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    end
    return Mint(u)
end

function Base.:/(x::Mint, y::Mint)
    return x * inverse(y)
end

function pow(x::Mint, n::Int64)
    ret = Mint(1)
    while n > 0
        if n & 1 != 0
            ret *= x
        end
        x *= x
        n >>= 1
    end
    return ret
end

end

using .Modulo

n, p = parseInt()
memo = fill(false, n + 1, n + 1)
dp = fill(Mint(0), n + 1, n + 1)

function f(i::Int64, j::Int64)
    # iを分割する(大きさj以下のグループに分ける)
    if memo[i+1, j+1]
        return dp[i+1, j+1]
    end
    if i == 0
        dp[i+1, j+1] = Mint(1)
        memo[i+1, j+1] = true
        return Mint(1)
    end
    if i == 1
        dp[i+1, j+1] = Mint(0)
        memo[i+1, j+1] = true
        return Mint(0)
    end

    ret = Mint(0)
    for k = 2:j
        if k == p
            continue
        end
        for l = 1:i÷k
            ret += pow(Mint(1) / Mint(k), l) * f(i - k * l, k - 1)
        end
    end
    dp[i+1, j+1] = ret
    memo[i+1, j+1] = true
    return ret
end

function main()
    factn = Mint(1)
    for i = 2:n
        factn *= Mint(i)
    end
    (factn * f(n, n)).m |> println
end

main()
0