drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AtCoder AtCoder600点 ABC-G 赤色diff 数え上げ問題 グラフ・盤面・数列の個数の数え上げ 制約:数値が10^6以下 考察：場合分けして考える 平方分割 場合分け：小さい場合は愚直に解ける 数量が小さいことの活用：約数の個数 考察：一部の変数を固定して考える Greedy 対象を一意に定める操作列を数え上げる 入力が定数個 NoviSteps4D コンテスト後に解いた。なんとか詰め切った。 問題へのリンク 問題概要 非負整数 と整数 に対して、関数 を次のように定義する。 正整数 が与えられて、次の条件を満たす非負整数列 と正の整数 の組の個数を 998244353 で割った余りを求めよ。 () 制約 考えたこと が大きくなると が小さく済むことなどに着目して、丁寧に場合分けして考えることにした。 まず、そもそも が の約数に限られることが容易に分かるので、この値を固定することにした (多くても 160 個程度)。 のとき 最初に、 の場合を処理することにした。それをしておけば、 の値は常に 10 通りと考えてよくなる。 の値を固定して… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2023%2F10%2F01%2F195226" title="AtCoder ABC 322 G - Two Kinds of Base (4D, 赤色, 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/1687765056723440 Hatena Blog https://hatena.blog 2023-10-01 19:52:26 rich https://drken1215.hatenablog.com/entry/2023/10/01/195226 1.0 100%