AC代碼

https://codeforces.com/contest/1740/submission/178776936

https://codeforces.com/contest/1740/submission/178913917

題意：

給Pak Chanek一個(gè)n個(gè)整數(shù)的數(shù)組a。對(duì)于每個(gè)i（1≤i≤n） ，Pak Chanek將在白板上寫一個(gè)元素集{ai}。

之后，在一次操作中，Pak Chanek可能會(huì)執(zhí)行以下操作：

1. 在白板上選擇兩個(gè)不同的S和T, S∩T =? （S和T沒(méi)有任何共同的元素）。

2. 從白板上擦除S和T并在白板上寫下S∪T（S和T的結(jié)合）。

執(zhí)行零次或多次操作后，Pak Chanek將構(gòu)造一個(gè)集合M，其中包含寫在白板上的所有集合的大小。

換句話說(shuō)，M中的每個(gè)元素對(duì)應(yīng)于操作之后的某一個(gè)集合的大小。

求不同集合M的數(shù)量 模998244353。

題解：

組合數(shù)學(xué) + DP + 滾動(dòng)數(shù)組

dp[j][i][left]: 劃分i 個(gè)集合時(shí)，最后一個(gè)集合用掉的元素個(gè)數(shù)不小于j，且剩余元素個(gè)數(shù)為left

dp[j][i+1][mx-j] 為下列狀態(tài)的個(gè)數(shù):?

劃分i+1個(gè)集合，最后一個(gè)集合用掉的元素個(gè)數(shù)為j，且剩余元素個(gè)數(shù)為mx-j

集合的大小非遞增，第i+1個(gè)集合最多可用元素個(gè)數(shù)mx=dat[i]+left