対象を一意に定める操作列を数え上げる
AtCoder
AtCoder800点
AGC-C
数え上げ問題
0と1と2の問題
特定の場所を決め打つことで単純な場合に帰着する
二項係数
差分更新
パリティ
必要条件を列挙したら十分条件になる
判定関数を考える
操作
操作:2つのものを1つにマージ
入力が定数個
変数変換して扱いやすい同型な問題を見出す
条件の言い換え
今が良いほど未来も良いGreedy
Greedy
対象を一意に定める操作列を数え上げる
橙色diff
これまた楽しい数え上げ！！！ 解説があまりにも天才だけど、解説の方法が思いつかなくても一応できた！！！ 問題へのリンク editorial 解説放送 問題概要 "A", "B", "C" のみからなる長さ の文字列であって、以下の条件を満たすものの個数を 998244353 で割…
AtCoder
AtCoder600点
ARC-D
黄色diff
DP
数え上げ問題
入力が定数個
2^K
DP高速化
DP高速化:累積和
賢い漸化式
総和一定制約の数え上げ
制約条件:総和が一定
対象を一意に定める操作列を数え上げる
全体を2倍する
いろんな DP が考えられそう！ 問題へのリンク editorial 問題概要 正整数 が与えらる。以下の条件を全て満たす有理数の多重集合は何種類存在するか、998244353 で割ったあまりを求めよ。 多重集合の要素数は 多重集合の要素の総和は 多重集合の要素は全て (…
AtCoder
AtCoder600点
ABC-F
数え上げ問題
順列
順列を巡回群の直積と見る
最小添字規則によってダブルカウントを防ぐ
DP
区間分割型ナップサックDP
数珠
グラフ・盤面・数列の個数の数え上げ
二項係数
条件の言い換え
K以上からK+1以上を引く
調和級数
対象を一意に定める操作列を数え上げる
連結成分
グラフ問題
多項式・形式的冪級数
形式的冪級数の高等演算
橙色diff
結構いろんな考え方のできる問題！ 問題へのリンク 問題概要 頂点数 、辺数 の無向グラフであって、次の条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。 自己ループを持たない すべての頂点の次数が 2 以下である 各連結成分のサイズを並べた…
