drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AtCoder AtCoder600点 ARC-D 黄色diff DP 数え上げ問題 入力が定数個 2^K DP高速化 DP高速化:累積和 賢い漸化式 制約条件:総和=K 対象を一意に定める操作列を数え上げる テク:全体を2倍する いろんな DP が考えられそう！ 問題へのリンク editorial 問題概要 正整数 が与えらる。以下の条件を全て満たす有理数の多重集合は何種類存在するか、998244353 で割ったあまりを求めよ。 多重集合の要素数は 多重集合の要素の総和は 多重集合の要素は全て ( は非負整数) の形 制約 解法 (1)：僕の考えた解法 想定解法とは違う解法でやった。「条件を満たす対象を一意に定めるような操作列を考えて、それを数え上げる」というのも一つの典型だと思う。 まず、今回の数列は次のような操作によって一意に定められることに注意する。 まず 1 のうちのいくつかを分裂させる ex: (1, 1, … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2020%2F11%2F01%2F175900" title="AtCoder ARC 107 D - Number of Multisets (黄色, 600 点) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/80936665/1516148889515660 Hatena Blog https://hatena.blog 2020-11-01 17:59:00 rich https://drken1215.hatenablog.com/entry/2020/11/01/175900 1.0 100%