結果

問題 No.2468 Mercurialist
ユーザー 👑 SPD_9X2SPD_9X2
提出日時 2023-05-09 07:50:28
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 300 ms / 2,000 ms
コード長 2,598 bytes
コンパイル時間 280 ms
コンパイル使用メモリ 82,168 KB
実行使用メモリ 113,704 KB
最終ジャッジ日時 2024-11-20 18:57:13
合計ジャッジ時間 6,901 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

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