drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AtCoder AtCoder700点 ARC-D 多項式・FPS(形式的冪級数) Bostan-Mori法 制約条件:総和=K 二項係数 負の二項係数 入力が定数個 対象を一意に定める操作列を数え上げる 数え上げ問題 グラフ・盤面・数列の個数の数え上げ 操作後の結果の数え上げ 操作 橙色diff FPS(形式的冪級数)の高等演算 FPSテク:漸化式の母関数を求める 重複組合せ 数列 Greedy：先に進むほど新たな選択肢が挿入される 包除原理 制約条件:xi<=ai FPS による考察はやっぱり強力ですね！ 問題へのリンク 問題概要 長さ かつ総和 である非負整数列 のうち、以下の条件を満たすものの個数を 998244353 で割ったあまりを求めよ。 「以下の操作のうちどちらかを選んで行うことを繰り返して、 の全ての要素を 0 にすることが出来る。」 操作 1： を満たす整数 を選び、 を 減らす 操作 2： を満たす整数 を選び、 を 1 ずつ減らす 制約 考えたこと：操作列の数え上げに帰着する 操作によって出来上がるものが何通りあるかを数え上げる問題では、大きく分けて 操作によって作れるかどうかの判定問題をまず解く 各対象物を作るための操作列が一意とな… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2023%2F05%2F15%2F024900" title="AtCoder ARC 160 D - Mahjong (橙色, 700 点) - けんちょんの競プロ精進記録" 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 2023-05-15 02:49:00 rich https://drken1215.hatenablog.com/entry/2023/05/15/024900 1.0 100%