[2021 NPSC高中組網路賽]殿壬的飲料王國
出處: 2021 NPSC網際網路程式設計大賽高中組網路賽pA
殿壬是個天才兒童，他在⼀個⽉⼤的時候就學會數數、六個⽉⼤的時候就學會乘法跟除法、⼀歲時學會寫程式、⼀歲⼜六個⽉時養了可愛的拉布拉多、⼀歲⼜⼗個⽉時養了可愛的貓咪、兩歲時發明了「吃餅乾」的遊戲、三歲⼜三個⽉⼤時成功地對貓咪做了排序。現在要講的是殿壬三歲⼜四個⽉的故事。
殿壬在三歲⼜四個⽉的時候創⽴了⼀個飲料王國，這個王國⼀共有 \(N\) 種⾯額的貨幣，⾯額⼤⼩分別為 \(1, 2, . . . , N\) 元。某⼀天，王國中的 \(N × M\) 位⼩朋友想⼀起去飲料王國中最有名的飲料店「億園」買飲料，「億園」之所以有名是因為他販售了史上最好喝的飲料「ＱＱ捏捏好喝 到殿壬茶」，⽽且只需要花 \(1\) 元就能購買。這 \(N × M\) 位⼩朋友中，有 \(M\) 位恰有⼀張⾯額為 \(1\) 元的貨幣、\(M\) 位⼩朋友恰有⼀張⾯額為 2 元的貨幣、· · · 、\(M\) 位⼩朋友恰有⼀張⾯額為 \(N\) 元的 貨幣。這 \(N × M\) 位⼩朋友都想去買「ＱＱ捏捏好喝到殿壬茶」，然⽽因為⼈數實在太多，殿壬 只好將⼩朋友們分成紅⽩兩隊，讓紅隊的⼈先去買飲料，等紅隊的所有⼈買完再讓⽩隊的⼈去 買飲料。已知殿壬在幫⼩朋友們分完隊伍後，紅⽩兩隊當中，分別有 \(a_i\), \(b_i\) 位⼩朋友持有 \(i\) 元貨幣。
⾝為「億園」飲料店唯⼀店員的你，每次只能接受⼀張訂單，將⼿上唯⼀⼀張訂單處理完後才能受理下⼀位客⼈點餐。然⽽店⾯開張當天，你發現了⼀個⼤問題，那就是收銀機完全沒 有任何的零錢，也就是沒有辦法找零。無奈之下你只能使⽤客⼈們⽀付的零錢進⾏找零，於是你希望⼩朋友們能以「完美的」順序排隊，使得每⼀位⼩朋友在點餐時，你都有⾜夠的零錢可 以⽀付找零，也就是說，如果⼀位⼩朋友⽀付了⾯額為 \(x\) 元的貨幣，你必須能夠恰好找給他 \(x-1\) 元。
好奇⼼旺盛的你，想知道⼩朋友們有幾種「完美的」排隊順序可以讓你順利的為每位⼩朋友進⾏找零。在兩種排隊順序中，只要存在正整數 \(k\) 使得你在這兩個排隊順序中服務的第 \(k\) 位 ⼩朋友是不同⼈，那它們就是不相同的排隊順序。因為答案可能很⼤，所以只需要計算其除以 \(998244353\) 之後的餘數就可以了。
輸入格式
輸⼊第⼀⾏包含兩個正整數 N, M。
接下來共有 \(N\) ⾏，其中第 \(i\) ⾏包含兩個整數 \(a_i, b_i\)，分別代表紅隊與⽩隊中持有 \(i\) 元貨幣的⼩朋友⼈數。
- \(1 ≤ \)N × M\( ≤ 106\)
- \(0 ≤ a_i, b_i ≤ M\)
- \(a_i + b_i = M\)
輸出格式
請輸出⼀個整數，代表⼀共有幾種「完美的」排隊順序除以 \(998244353\) 後的餘數。
提示
在範例輸入1中，假設 \(x_1, x_2\) 是兩位恰有⼀張⾯額為 \(1\) 元的⼩朋友，\(y_1, y_2\) 是兩位恰有⼀張⾯額為 \(2\) 元的⼩朋友，並且 \((x_1, x_2, y_1)\) 隸屬於紅隊，\((y_2)\) 隸屬於⽩隊，那麼所有完美的排隊順序如下：
- \(x_1, x_2, y_1, y_2\)
- \(x_2, x_1, y_1, y_2\)
- \(x_1, y_1, x_2, y_2\)
- \(x_2, y_1, x_1, y_2\)
範例輸入1
2 2
2 0
1 1範例輸出1
4範例輸入2
3 2
2 0
2 0
1 1範例輸出2
20
评论
想問子題7是不是超出 N*M <= 106 的限制
edit: 剛去查原題發現是1e6 那沒事了
非常好楊表+鉤子定理+DP+模逆元
使我排列組合100分
NPSC好狠
恭喜你解出來了!
本題調整記憶體上限，已調整為當初比賽的限制1G，並已重新Rejudge本題所有提交紀錄