OMC139(F)

整数論的考察によってかなり簡単に解くことができます. 補題を知っていれば600点ぐらいの難易度に感じたかも知れません.

まずは本解通り$$S=\sum_{\sum a_i=N}\left(\dfrac{N!}{\prod a_i!}\times \prod a_i^i\right)$$を得る. ここで次の補題を使う:

補題.

$p$を素数とし, $\displaystyle N=\sum_{i=1}^m a_i$ とする. ここで $N, a_i$ は非負整数, $m$ は正整数である. さらに $\displaystyle a_i=\sum_jb_{i, j}p^j,\ N=\sum_{j}n_jp^j$ と $p$ 進展開する. このとき $$\dfrac{N!}{\prod a_i!}\equiv\begin{cases}0&(\mathrm{if}\ \exists j, s.t. \sum_ib_{i,j}\neq n_j)\\\displaystyle\prod_j\dfrac{n_j!}{\prod_i b_{i, j}!}&(\mathrm{otherwise})\end{cases}\pmod p$$ (前者の時は の$p$進での足し算に繰り上がりがあるとき, 後者は繰り上がりがないときである)

証明.

$\displaystyle s_i=\sum_{k=1}^ia_k$ とすると, $P=\displaystyle\dfrac{N!}{\prod a_i!}=\prod_i {}_{s_i}\mathrm{C}_{a_i}$ となる. ここでKummerの定理を用いながら $P\equiv 0\pmod p$ か否かで場合分けをし, Lucasの定理を用いることで補題を得る.

$N=4p+7$ が $p$ 進数での表記なので $a_i=pb_i+c_i$ と $p$ 進数で表記すると

$$S\equiv\sum_{\sum b_i=4}\sum_{\sum c_j=7}\dfrac{4!}{\prod b_i!}\cdot\dfrac{7!}{\prod c_j!}\cdot\prod c_j^j\equiv6^4\cdot\dfrac{7!}{2}\cdot\sum_{i=1}^62^i\equiv 6^4\cdot7!\cdot(2^6-1)\equiv\mathbf{411505920}\pmod p$$

となる. ここで $\displaystyle\sum_{j=1}^6c_j=7$ ならば $(c_j)$ は $(2,1,1,1,1,1)$ の並べ替えしかあり得ないことを使った.

補題について一言. 良く用いられるLucasの定理などは $n$ 個の中から $m$ 個選ぶ方法の個数を $p$ で割った余りなどを考えますが, これを拡張するなら $n$ 個の中から $m_1$ 個選び, その後 $m_2$ 個選び... (別のタイミングで選んだものは区別する) という方法の個数を $p$ で割った余りを考えたくなると思います. 従ってこの拡張は自然なものと考えることが出来るでしょう.