betrue12 https://blog.hatena.ne.jp/betrue12/ ARMERIA https://betrue12.hateblo.jp/ AtCoder プログラミング 競技プログラミング 先日のコンテストの問題における、最後の高速化について知りたいというリクエストがあったため、解説を書きます。より一般的な「個数制限付き部分和問題+条件を満たす選び方の数え上げ」という枠組みで説明します。 扱う問題 正整数 と、正整数からなる長さ の数列 が与えられる。 を 個以上 個以下、 を 個以上 個以下…と選ぶ方法のうち、その総和が であるような方法の個数を で割った余りを求めよ。 より形式的には、以下の条件を満たす非負整数列 の個数を で割った余りを求めよ。 全ての に対して この問題を全体計算量 で解きます。 解法 普通の部分和問題と同様にDPをします。状態を以下のように定義します。 … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbetrue12.hateblo.jp%2Fentry%2F2020%2F10%2F05%2F124052" title="個数制限付き部分和問題+条件を満たす選び方の数え上げ - ARMERIA" 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/106916089/1592411661884548 Hatena Blog https://hatena.blog 2020-10-05 12:40:52 rich https://betrue12.hateblo.jp/entry/2020/10/05/124052 1.0 100%