competitive

問題 $F(M) =$長さ$N$の順列で、すべてのサイクルの長さが$M$の約数であるようなものの数 $f(m)=$長さ$N$の順列で、サイクルの長さのLCMが$m$であるようなものの数 とするとき、求める数は$N$の分割のLCMとして得られるようなすべての$...

問題 AC $h_i$が互いに異なる場合は$(2N-1)!! = (2N)! / 2^N N!$通りという有名事実がある（後述）。以下、$p_i = (2i-1)!!$とする。 身長$h$の人が$a_h$人いるとする。$i$人の同じ身長を持つ人から$j$ペ...

問題 $2(s_1+n_1+u_1+k_1+e_1)+\Delta s + \Delta n + \Delta u + \Delta k + \Delta e \le N$で各変数は非負という条件下で$\Delta s\Delta n\Delta u\Delt...

問題 AC 求める数を$a_n$とする。長さ$n$の順列を先頭$k$要素が$1, 2, ..., k$の順列であるような最小の$k$で分類して数えると、それぞれ$a_k(n-k)!$通りある。長さ$n$の順列から長さ$n+1$の順列を作ることを考えると、$n...

問題 AC 問題: 無向グラフが与えられる。出次数の最大値が最小であるようなacyclic orientationを求めよ。 出次数が$D$以下であるacyclic orientationが存在するかどうかの判定問題が解ければよい。判定問題は次のように解け...

問題 提出 与えられた数列を$(a_i)_{i = 0}^\infty \ (a_0=0, a_1 = 2, a_2 = 22, ...)$とする。$M = \begin{bmatrix} 10 & 2 \\ 0 & 1\end{bmatri...

問題 AC 分割数っぽい数え上げなので分割数っぽいDPを考える。 まずは分割数のDPを思い出す。自然数$n$を$k$個の正整数の和に分割する場合の数を$P(n, k)$とする。分割の中に1を含まないものは$n-k$の$k$分割のすべての項を$1$増加させて...