beet's soil

競プロのことなど

ARC061 F - 3人でカードゲーム / Card Game for Three

1000↑は考察の流れを残そうと思う(自分用)

とりあえず和をS = N+M+K とおく

ちょうどX枚で終了するをN~Sまで回す

X枚で終了するとき 3^(S-X)枚は自由
最後の1枚はA
X-1枚中N-1枚はA comb(X-1,N-1)
BはM枚以下、CはK枚以下
X-N枚の中にBがY枚 -> 部分点500
DPで求められないか?無理そう
どこかで独立にならないか?

BがY枚、CがZ枚で終了するとき
X-N = Y+Z

二乗DPは回らない

3*10^5でFFTは鬼 任意MODのNTTは地獄

O(MK) で二乗DPは自明


Σ_{x+y=s,0≤x≤a,0≤y≤b} sCx を DPで求められないと不可能でしょ

dp[0]=1
dp[t]=Bが0~Mまいで合計t枚になるような通り数
tight1[t]=BがM枚で合計t枚 tCM
tight2[t]=CがK枚で合計t枚 tCK
dp[t+1]= +(dp[t]-tight1[t]) Bを末尾に追加
+(dp[t]-tight2[t]) Cを末尾に追加

サンプル試す→合った AC