hamayanhamayan https://blog.hatena.ne.jp/hamayanhamayan/ はまやんはまやんはまやん https://blog.hamayanhamayan.com/ 競技プログラミング https://yukicoder.me/problems/no/917 前提知識 動的計画法 解説 https://yukicoder.me/submissions/393368 制約が少し特殊っぽい。 よくある方針として、全通りからgcdが1とならないものを引く方針で考える？ 包除原理な感じもする。 いや、1つ使う要素を固定して、DPすればdpの添字はそれの約数に収まるな。 それで解けそう。 A1, A2, ...と順番にA[i]を使うときに最大公約数が1となる部分列の個数を求める。 このとき、A[i]を使うと決めたら、j<iを満たすA[j]は使う組み合わせは求まっているので、A[j]はす… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.hamayanhamayan.com%2Fentry%2F2019%2F10%2F26%2F102535" title="Make One With GCD [yukicoder 917] - はまやんはまやんはまやん" 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 2019-10-26 10:25:35 rich https://blog.hamayanhamayan.com/entry/2019/10/26/102535 1.0 100%