二項係数と多項式展開による係数計算
多項式 $(ax + by)^k$ を展開したとき、項 $x^n y^m$ の係数を $10007$ で割った余りとして求めよ。ただし、$n + m = k$ が常に成り立つ。
解法の概要
二項定理より、$(ax + by)^k$ の展開における $x^n y^m$ 項の係数は以下の式で表される：
$$
\binom{k}{n} \cdot a^n \cdot b^m
$$
ここで $\binom{k}{n}$ は二項係数であり、$k \leq 1000$ であるため、動的計画法（パ ...
5月31日 20:30 投稿
CF1228E Another Filling the Grid の解法
すべての行に少なくとも 1 つの 1 を配置する必要があるため、行ごとに処理し、その行にいくつかの 1 を追加することを考えます。現在の状態を表すために、dp[i][j] を「最初の i 行を埋めた時点で、1 がすでに存在する列が j 列ある場合の埋め方の総数」と定義します。遷移では、現在の行で新たに 1 を追加する位置の数を k とし、残りの位置には任意の値を入れます。
\[ ...
5月22日 16:27 投稿