#二項係数 まず, 愚直な dp を考える. rep(i, sz) rep(j, sz(s) + 1) rep(l, 26) { if (s[j] - 'a' == l) add(dp[i + 1][j + 1], dp[i][j]); else add(dp[i + 1][j], dp[i][j]); } cout << dp[sz][sz(s)] << endl; rep(l, 26) をなくすと以下のようになる. r…

問題 n * m の, 0, 1 のマスが与えられる. 2 人でゲームをする. 各ターン, あるマスの行, 列で, 1 のマスがないマスを 1 にできる (隣とは限らないよ). 相手が 1 にできなくなったら勝ち. 解法 1 のマスがない行, 列の個数をそれぞれ数える. それらの小さい…

問題 を 1, ..., n の permutation として, を最大化する. 解法 で, mod をとってできるだけ小さくならないようにする, と考えない. mod をとる側で, できるだけ大きくしようとする. mod 1 で最大は 0. mod 2 で最大は 1. のように. とすれば最大値が達成で…

問題 木と, 各頂点で得るべき数が与えられる. 各頂点で得る数は, 隣り合う頂点で, すでに数を得た頂点の数にない数の最小値. どの順番で頂点が数を得るか求める. 解法 各頂点, 得るべき数と得る数を一致させる. 得るべき頂点. 数 x を得るべき頂点において, …