結果

問題 No.2468 Mercurialist
ユーザー 👑 SPD_9X2SPD_9X2
提出日時 2023-05-09 07:50:28
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 339 ms / 2,000 ms
コード長 2,598 bytes
コンパイル時間 346 ms
コンパイル使用メモリ 87,304 KB
実行使用メモリ 115,400 KB
最終ジャッジ日時 2023-08-13 02:37:18
合計ジャッジ時間 9,009 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 139 ms
109,312 KB
testcase_01 AC 141 ms
109,260 KB
testcase_02 AC 140 ms
109,340 KB
testcase_03 AC 315 ms
111,036 KB
testcase_04 AC 316 ms
114,540 KB
testcase_05 AC 339 ms
113,364 KB
testcase_06 AC 167 ms
114,752 KB
testcase_07 AC 161 ms
112,120 KB
testcase_08 AC 293 ms
110,112 KB
testcase_09 AC 140 ms
109,204 KB
testcase_10 AC 286 ms
110,072 KB
testcase_11 AC 149 ms
109,852 KB
testcase_12 AC 138 ms
109,156 KB
testcase_13 AC 138 ms
109,356 KB
testcase_14 AC 300 ms
112,184 KB
testcase_15 AC 161 ms
111,544 KB
testcase_16 AC 158 ms
111,724 KB
testcase_17 AC 159 ms
111,872 KB
testcase_18 AC 231 ms
112,816 KB
testcase_19 AC 235 ms
110,928 KB
testcase_20 AC 243 ms
111,144 KB
testcase_21 AC 280 ms
114,208 KB
testcase_22 AC 151 ms
109,712 KB
testcase_23 AC 200 ms
115,400 KB
testcase_24 AC 208 ms
112,512 KB
testcase_25 AC 196 ms
114,512 KB
testcase_26 AC 204 ms
110,748 KB
testcase_27 AC 195 ms
112,960 KB
testcase_28 AC 290 ms
113,944 KB
testcase_29 AC 185 ms
113,584 KB
testcase_30 AC 183 ms
112,712 KB
testcase_31 AC 263 ms
111,708 KB
testcase_32 AC 223 ms
111,392 KB
testcase_33 AC 197 ms
113,512 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""

Mercurialist 想定解 v0.0

O(X+Y+Z) で解く

X,Zは区別せず、Yだけ区別して考える。
全ての通り数は nCr(X+Y+Z,X) * nCr(Y+Z,Y) * Y!

生きている通り数を数えあげる。
i日目に最初のエリクシールが来る場合～
をi = 0 , ... ,X+Y+Z-1 まで全探索する(0-indexed)

N = X+Y+Z とする。
まず、X-1 個のエリクシールをiより右の N-1-i 個の空いている日に入れる
nCr (N-1-i , X-1) 通り

次に、水銀を "死亡までの日数が短い順" に位置を決めていく。

水銀の置ける箇所は…
4個置く,K=2 の場合…

|ooooo -> 5*4*3*2
o|oooo -> 5*4*3*2
oo|ooo -> 5*4*3*2
ooo|oo -> 4*4*3*2
oooo|o -> 3*3*3*2
ooooo| -> 2*2*2*2

|ooooooo -> 7*6*5*4
o|oooooo -> 7*6*5*4
oo|ooooo -> 7*6*5*4
ooo|oooo -> 6*6*5*4
oooo|ooo -> 5*5*5*4
ooooo|oo -> 4*4*4*4
oooooo|o -> 3*3*3*3
ooooooo| -> 2*2*2*2

のように変化する

1 1 1 1の場合, 6通りの内
YZXだけ死ぬ

多分これでok?

"""

import sys
from sys import stdin
from collections import deque

def modfac(n, MOD):
 
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs

def nCr(n,r):
    if n < r or n < 0:
        return 0
    return faclis[n] * invlis[n-r] * invlis[r] % mod

mod = 998244353
faclis,invlis = modfac(400000,mod)

def getinv(x):
    return pow(x,mod-2,mod)

X,Y,Z,K = map(int,stdin.readline().split())
N = X+Y+Z

# 0日目に最初のエリクシールが来る時の水銀の置き方を求めておく
hg_place_part = 1
hg_queue = deque()

for j in range(Y):
    hg_place_part *= N-X-j
    hg_place_part %= mod
    hg_queue.append( N-X-j )

ans_n = 0 #求める確率の分子

for i in range(X+Y+Z): #i日目が最初のエリクシールの場合

    if N-1-i < X-1:
        break

    right = N-1-i #i番目よりも右のマスの数
    right_notX = right - (X-1) #i番目よりも右、Xでないマスの数

    hg_place = hg_place_part * pow(right_notX + K , Y-len(hg_queue) , mod) % mod
    ans_n += nCr(N-1-i,X-1) * hg_place
    ans_n %= mod

    #print (i,hg_queue,right_notX+K)

    # hg_place の更新
    if i >= K and hg_queue: # <=かも? 
        hg_place_part *= getinv( hg_queue.popleft() )
        hg_place_part %= mod

ans_d = nCr(X+Y+Z,X) * nCr(Y+Z,Y) * faclis[Y] % mod

print (ans_n,file=sys.stderr)
print (ans_n * getinv(ans_d) % mod)
0