結果

問題 No.2468 Mercurialist
ユーザー 👑 SPD_9X2SPD_9X2
提出日時 2023-05-09 07:50:28
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 298 ms / 2,000 ms
コード長 2,598 bytes
コンパイル時間 256 ms
コンパイル使用メモリ 82,508 KB
実行使用メモリ 113,896 KB
最終ジャッジ日時 2024-04-30 21:04:33
合計ジャッジ時間 6,643 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 84 ms
94,720 KB
testcase_01 AC 82 ms
93,592 KB
testcase_02 AC 82 ms
93,520 KB
testcase_03 AC 266 ms
110,472 KB
testcase_04 AC 273 ms
113,528 KB
testcase_05 AC 298 ms
112,808 KB
testcase_06 AC 116 ms
113,224 KB
testcase_07 AC 104 ms
108,712 KB
testcase_08 AC 248 ms
105,956 KB
testcase_09 AC 88 ms
94,488 KB
testcase_10 AC 237 ms
103,296 KB
testcase_11 AC 92 ms
96,076 KB
testcase_12 AC 83 ms
93,292 KB
testcase_13 AC 83 ms
93,676 KB
testcase_14 AC 249 ms
110,464 KB
testcase_15 AC 108 ms
107,632 KB
testcase_16 AC 105 ms
108,000 KB
testcase_17 AC 105 ms
108,056 KB
testcase_18 AC 187 ms
111,580 KB
testcase_19 AC 187 ms
109,572 KB
testcase_20 AC 195 ms
110,712 KB
testcase_21 AC 234 ms
113,896 KB
testcase_22 AC 96 ms
101,568 KB
testcase_23 AC 147 ms
112,664 KB
testcase_24 AC 160 ms
111,036 KB
testcase_25 AC 147 ms
113,348 KB
testcase_26 AC 156 ms
110,240 KB
testcase_27 AC 146 ms
111,388 KB
testcase_28 AC 244 ms
113,296 KB
testcase_29 AC 141 ms
112,608 KB
testcase_30 AC 133 ms
110,204 KB
testcase_31 AC 217 ms
111,244 KB
testcase_32 AC 174 ms
110,736 KB
testcase_33 AC 144 ms
112,300 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