分割数
YosupoLibraryChecker
分割数
写像12相
多項式・FPS(形式的冪級数)
FPS(形式的冪級数)の高等演算
FPSテク:f=exp(log(f))
Eulerの五角数定理
各kに対して
数え上げ問題
ここでは の計算量の解法を実装した。本当は FPS を使えば の計算量でできる。 問題へのリンク 問題概要 非負整数値 が与えられる。 の分割数を 998244353 で割った余りを求めよ。 制約 考えたこと ここでは、この記事に書いた の計算量の解法を実装した。 q…
分割数で鮮やかに解ける！ 問題へのリンク 問題概要 人のクラスで総額 円を集めることにした。 このクラスの生徒は皆見栄っ張りであり、出席番号順が１つ前の生徒に比べて 円以上高い金額を寄付しないと気が済まない。 この条件を満たす方法の個数を 1000000…
AtCoder
AtCoder500点
unrated公式コン
分割数
数え上げ問題
賢い漸化式
漸化式
DP
グラフ・盤面・数列の個数の数え上げ
前処理
写像12相
現実世界の題材を扱った問題
アニメやゲームを元ネタとした問題
トーナメントなど対戦表に関する問題
分割数のいい感じの問題！ 問題へのリンク 問題概要 長さ の数列 killA, killB が与えられる。この 2 つの広義単調減少である。 次の条件を満たす長さ の数列 deathA, deathB の組の個数を 1000000007 で割ったあまりを求めよ。 killA の総和 = deathB の総…
こないだのドワンゴからの挑戦状で、分割数を用いる問題が出題されたので、周辺の話題を整理してみました。 数え上げに関する話題として分割数やスターリング数は時折登場しますが、どちらも写像12相と呼ばれる広い枠組みに含まれています。今回は分割数を、…
