AtCoder Regular Contest 102 E - Stop. Otherwise...

E - Stop. Otherwise...

問題

互いに区別しない $K$ 面サイコロを $N$ 個振る。どの異なる $2$ つのサイコロの出目の和も $i\ (=2,\ 3,\ ...,\ 2K)\$ にならないような出目の組の場合の数を $998244353$ で割った余りを求めよ。

制約

$1 \leq K \leq 2000$
$2 \leq N \leq 2000$

解法

解説pdfとは異なり、包除原理を用いて解いた。

まず、区別しない $K$ 面サイコロの出目の組は ${}_KH_N$ 通りである。

問題文の条件は以下のように置き換えられる。

$a$ と $i-a$ は同時に出ない
$a+1$ と $i-(a+1)$ は同時に出ない
$\vdots$
$b$ と $i-b$ は同時に出ない

この条件の個数を $q$ とすると、
$\begin{eqnarray} q=\left\{ \begin{array}{ll} \left\lfloor \frac{i}{2} \right\rfloor & (i\leq k+1) \\ K-\left\lfloor \frac{i}{2} \right\rfloor+1 & (i> k+1) \\ \end{array} \right. \end{eqnarray}$

包除原理を用いると、
$\begin{eqnarray}\mbox{（求める場合の数）} &=& \mbox{（条件を0個以上満たさない場合の数）} \\ &\quad& - \mbox{（条件を1個以上満たさない場合の数）}\\ &\quad& + \mbox{（条件を2個以上満たさない場合の数）}\\ &\quad& \vdots \\ &\quad& +(-1)^q \times \!\!\! \mbox{（条件を}q\mbox{個以上満たさない場合の数）} \\ &=& \sum_{p=0}^{q} (-1)^p \times {}_qC_p \times {}_KH_{N-2p} \end{eqnarray}$