問題リンク： codeforces.com
問題概要
本質部分だけ抜き出して書いてます.
$ N $ 個の閉区間, $ I_{i}=[ l_{i}, r_{i}] $ が与えられます. $k=1,2,\dots,N$ に対して以下の問題を解いてください.
$ k $ 個の添え字の組 $i_{1}, i_{2},\dots,i_{k}$ であって $\displaystyle\bigcap_{j=1}^{k} I_{i_{j}}$ が空でないものの個数を $998244353$ で割った余りを求めてください.
解説
以下 $\displaystyle\binom{n}{k}=\dfrac{n!}{(n-k)!k!}$ は二項係数とし, $n \lt k$ のときは $0$ と定めます.
適当に座圧したのちに $T=\max\lbrace r_{i} \mid 1 \leq i \leq N \rbrace$ とします. また, 各 $t=1,2,\dots,T$ に対して $t \in I_{i}$ となる $i$ の個数を $C_{t}$ とします.
安直な考えですが, $\displaystyle\sum_{t}\displaystyle\binom{C_{t}}{k}$ を考えてみましょう.
もちろん, このままでは同一の組を複数回数えてしまうのでよくないです.
そこで, $t \in [ l_{i}, r_{i} - 1 ]$ となる $i$ の個数を $C^{\prime}_{t}$ とし, $\displaystyle\sum_{t}\displaystyle\binom{C^{\prime}_{t}}{k}$ を先ほどの値から引いてあげれば良いです.
このようにすることで, 任意の $S \subset \lbrace 1,2,\dots,N \rbrace$ に対し, $ S $ が $k = \lvert S \rvert$ の答えに加算されるのは $t = \min \lbrace r_{i} \mid i \in S \rbrace$ のときだけになります.
よって, 以下の問題を解くことに帰着されました.
長さ $T$ の数列 $C$ が与えられるので $k=1,2,\dots,N$ に対して $\displaystyle\sum_{t}\displaystyle\binom{C_{t}}{k}$ を求めよ.
$2$ 通りの方法で解きます.
畳み込みを用いる方法
$$\begin{align} \displaystyle\sum_{t}\displaystyle\binom{C_{t}}{k} & = \displaystyle\sum_{t}\dfrac{C_{t} ! }{(C_{t}-k)!k!} \\ & = \dfrac{1}{k!} \displaystyle\sum_{t}\dfrac{C_{t} ! }{(C_{t}-k)!} \end{align}$$ なので $f(x)=\displaystyle\sum_{t} C_{t} ! x^{C_{t}}, g(x) = \displaystyle\sum_{i = 0}^{\infty} \dfrac{x^{-i}}{i!}$ とすれば $\dfrac{1}{k!}[x^{k}] fg$ が答えとなります. 実装の際は, $C$ の最大値が高々 $N$ であることから $g(x) = \displaystyle\sum_{i = 0}^{N} \dfrac{x^{N-i}}{i!}$ として $fg$ の $k+N$ 次の係数を持ってくれば良いです.
Taylor Shift を用いる方法
$\displaystyle\sum_{t}\displaystyle\binom{C_{t}}{k} = [x^{k}]\displaystyle\sum_{t} (1+x)^{C_{t}}$ なので $f(x)=\displaystyle\sum_{t} x^{C_{t}}$ として $f(x+1)$ を求めれば良いです.
提出コード
