yosupo https://blog.hatena.ne.jp/yosupo/ よすぽの日記 https://yosupo.hatenablog.com/ 競技プログラミング 概要 遺跡発掘？ 何種類かのn個の建物があり、K個選ぶ。選んだ建物の種類一覧が与えられる。選び方は何通り？ サンプル 建物:{1, 2, 2, 1} 種類:{1, 2} 数:2 1, 2, 2, 1の中から2個選び出したら、1と2が入っていた(つまり1と2だった)選び方は？ もちろん(1の選び方)*(2の選び方)=2*2=4 建物:{1, 2, 2, 1} 種類:{1} 数:2 2個選んだら、1のみが入っていた つまり両方1だったという事なので1通り 制約 建物の種類は1~50 1≦n≦50 1≦k≦n 解法 DP d[i][j]:i番目までの種類でk個選ぶ選び方 d[i][j] = Σ(dp… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fyosupo.hatenablog.com%2Fentry%2F2013%2F07%2F18%2F001908" title="TopCoder SRM584 Div2 Hard Excavastions2 - よすぽの日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2013-07-18 00:19:08 rich https://yosupo.hatenablog.com/entry/2013/07/18/001908 1.0 100%