組合せ係数と対称性で数える
概要
組合せ係数・数え上げ
選択順・順列・分配を二項係数や階乗と対称性で式化する。
有限体部分空間のrank別計数
有限体上の部分空間をrankごとに分類し、Gaussian binomial係数などでspan条件を数え上げる。連立方程式を解く技能とは区別する。
Stirling変換と階乗基底変換
冪基底と下降階乗基底の係数をStirling数で相互変換し、rank別の計数列を目的の基底へ移す。
素数pのもとでもn≥pならn!は0になり、通常の階乗・逆階乗式は使えない。Lucasの定理はn,kのp進各桁についてC(n,k)=∏C(n_i,k_i) mod pと分解する。k_i>n_iの桁があれば0。0〜p−1の階乗を前計算し、ABC279 Exの巨大引数の係数計算へ接続する。
ABC234 Fのように文字の在庫から異なる文字列を数える場合を考える。入力: 処理済み文字種だけで作れる長さlの文字列数dp[l]と、新文字の在庫c。初期値は空文字列dp[0]=1。
変換: 新文字をk個使うなら、完成後のl+k個の位置から新文字の位置をk個選ぶ。残りの位置には元の文字列を順に入れるため、一対一対応から係数はC(l+k,k)。同じ文字同士は区別しないのでk!を掛けない。
出力: next[l+k]+=dp[l]C(l+k,k)を0≤k≤cで更新する。k=0も含め、最後は正の長さだけ足す。長さ上限まで階乗と逆階乗を用意する。
転用条件: 新しい要素が同一種類であり、元の相対順序が保存されることを確認する。ABC217 Gのラベルなし集合分割では、挿入位置でなく既存群への合流先を数える別のDPになる。
考え方
二項係数は位置集合の選択、multinomialは種類ごとの配置、Stirling数は集合の分割など、式の各因子に役割を持たせる。どの対象を区別しているかで同じ見かけの式の意味が変わる。
Gaussian二項係数を基底の重複から導く
qを素数冪とし、有限体F_q上のn次元空間のr次元部分空間数をG_q(n,r)と書く。まず、順序付きの独立なr本のベクトルを数える。i本を選んだ時点のspanにはq^i個のベクトルがあるので、次の選択肢はq^n−q^i個である。一方、同じr次元部分空間の順序付き基底は∏_{i=0}^{r−1}(q^r−q^i)通りある。したがって
G_q(n,r)=∏_{i=0}^{r−1}(q^n−q^i) / ∏_{i=0}^{r−1}(q^r−q^i)=∏_{i=1}^r(q^{n−r+i}−1)/(q^i−1)
となる。これがGaussian二項係数である。r=0の空積は1とし、r<0またはr>nなら0。F_2の3次元空間で一次元部分空間を数えると、非零ベクトル7個を各部分空間の非零ベクトル1個で割って7となる。F_3なら非零ベクトル26個を各部分空間の2個で割って13となり、ベクトル数と部分空間数の違いが見える。
rank別計数では、まずspanとなる部分空間を選び、その中で生成列を数える。固定したr次元部分空間Wをspanする順序付きm本のベクトルは、基底で座標化したr×m行列がfull row rankになる場合であり、∏_{i=0}^{r−1}(q^m−q^i)通り。よって、n次元空間のm本の生成列でrankがrのものはG_q(n,r)∏_{i=0}^{r−1}(q^m−q^i)通りである。指定ベクトルをspanに含む条件などがある場合は、それを満たす部分空間だけを選ぶよう最初の因子を変える。
有限体のサイズqと、答えを出力する法pは別の値である。上の商は整数として意味を持つが、法pで分母を逆元に置き換えるには各分母がpと互いに素でなければならない。素数pでもq^i−1≡0 mod pならこの式で除算できない。
除算を避ける計算法は次の漸化式である。
G_q(n,r)=G_q(n−1,r)+q^{n−r}G_q(n−1,r−1)
固定した(n−1)次元部分空間Hに含まれる場合が第一項。含まれない場合、Hとの交わりは(r−1)次元のWとなる。Hの外の固定ベクトルuを一つ取り、外へ出るベクトルをu+h(h∈H)の形に正規化すると、同じ部分空間を作るのはhの差がWに属するときである。したがって選択肢は|H/W|=q^{n−r}通りで、第二項になる。G_q(0,0)=1と範囲外0からDPすれば、任意の出力の法で計算できる。
Stirling数で冪と下降階乗を変換する
下降階乗をx_(k)=x(x−1)…(x−k+1)、x_(0)=1と書く。第二種Stirling数S(n,k)はn個の区別される要素をk個の空でないラベルなし群へ分ける数であり、
x^n=Σ_{k=0}^n S(n,k)x_(k)
が成り立つ。整数x≥0では、n個からx個への写像を、像の大きさkと同じ行き先の群へ分けて数えている。群を選ぶS(n,k)と、それぞれに異なる行き先を割り当てる下降階乗の積であり、同じ多項式なので一般のxにも成り立つ。
逆向きには、符号付き第一種Stirling数s(n,k)を下降階乗の冪係数として定義する。
x_(n)=Σ_{k=0}^n s(n,k)x^k
符号なし第一種Stirling数をc(n,k)と書く記法では、s(n,k)=(−1)^{n−k}c(n,k)である。たとえばx^3=x_(3)+3x_(2)+x_(1)、逆にx_(3)=x^3−3x^2+2xとなる。
入力が次数D以下の冪係数a_nで、P(x)=Σ_n a_n x^nを下降階乗基底の係数b_kへ直すなら、出力はb_k=Σ_{n=k}^D a_n S(n,k)。逆に下降階乗係数b_nから冪係数へ直すならa_k=Σ_{n=k}^D b_n s(n,k)である。変換の向きと添字をこの展開式から決める。
計数列に対するStirling変換は、同じ係数行列を別の向きで使う。t個の異なる対象へt個の群を割り当てる方法をF_tとし、m個の位置から繰り返し選ぶ列の数をG_mとすると、同じ対象を選ぶ位置が一つの群になり、G_m=Σ_{t=0}^m S(m,t)F_tとなる。逆変換はF_m=Σ_{t=0}^m s(m,t)G_t。ABC278 Exでは、この変換によって繰り返しを許す列のrank別計数から異なる要素を選ぶ列の計数へ戻す。多項式の係数変換と計数列の変換では、和を取る添字の向きが異なることに注意する。
標準的な計算はS(0,0)=s(0,0)=1、範囲外0から
S(n+1,k)=S(n,k−1)+kS(n,k)、s(n+1,k)=s(n,k−1)−n s(n,k)
で表を作る。第二種では新要素が一群を作るか既存のk群に入るかを分ける。第一種ではx_(n+1)=(x−n)x_(n)の係数を比べる。いずれも加減乗算だけであり、法上の除算を必要としない。
Lucasの桁分解を構成する
素数pでは(1+x)^p≡1+x^pだから、n=Σ_i n_i p^iに対して (1+x)^n≡∏_i(1+x^(p^i))^n_i。各因子から選べる次数は0,…,n_i<pの桁で、p進表記の一意性によりx^kの係数は∏_i C(n_i,k_i)になる。k_i>n_iの桁は選べず0。これが巨大nに対しても成立する根拠である。
0,…,p−1の階乗と逆階乗を作り、n,kをpで割って各剰余桁を取り、桁係数を掛けながら商へ進む。前計算O(p)時間・空間、query O(log_p(n+1))。p自体が巨大ならO(p)前計算は実用的でなく、必要な小係数の計算法も別に評価する。n<pのO(1)公式とLucasの全費用は同じではない。
成立条件と計算量
素数mod p、前計算上限N<pなら階乗・逆階乗をO(N)で作り二項係数O(1)。N≥pでは階乗が0になりLucasなどへ移る。重複選択、空集合、負の引数、対称性で割る根拠を確認する。
Gaussian二項係数はqの冪を前計算すれば一つの積の計算がO(r)回の法上の演算となる(逆元計算は別途必要)。q整数[i]_q=1+q+…+q^{i−1}とq階乗[i]_q!=∏_{j=1}^i[j]_qを使い、必要なq階乗が出力の法で可逆なら、上限NまでO(N)回の演算と逆元計算で前計算し、各係数をO(1)で得られる。除算を使わない漸化式はn≤N,r≤Rの範囲をO(NR)時間、行を使い回してO(R)空間で計算できる。
Stirling数の表はO(D²)時間・空間、表を用いた一つの係数列・計数列の変換はO(D²)時間。特定の一行のs(D,k)だけが必要なら、積∏_{i=0}^{D−1}(x−i)の係数を求めればよく、高速な多項式積を使う分割統治へ接続できる。ABC278 Exの大きな制約では二次時間の標準法だけでは足りず、公式解説の畳み込みによるrank別計数と第一種Stirling数の一行の計算を組み合わせる。必要なのが表全体、一行、変換後の列のどれかを先に確定する。
問題一覧
- ABC425 E「Count Sequences 2」 公式問題
- ABC405 E「Fruit Lineup」 公式問題組合せ: 法上の四則演算・高速累乗・逆元
技能・出典
主題: 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。)。主タグ: 組合せ係数・数え上げ / 補助タグ: 法上の四則演算・高速累乗・逆元
- ABC458 E「Count 123」 公式問題
- ABC358 E「Alphabet Tiles」 公式問題
- ABC234 F「Reordering」 公式問題組合せ: 法上の四則演算・高速累乗・逆元
技能・出典
主題: 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。)。主タグ: 組合せ係数・数え上げ / 補助タグ: 法上の四則演算・高速累乗・逆元
- ABC399 F「Range Power Sum」 公式問題
- ABC431 F「Almost Sorted 2」 公式問題
技能・出典
主題: 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。既習技能: 尺取り法・sliding windowで連続区間を走査する(一列の窓または二列の現在blockに関する不変条件を保ち、各pointerを単調に進められる。)。主タグ: 組合せ係数・数え上げ / 補助タグ: 尺取り法・sliding window
- ABC433 F「1122 Subsequence 2」 公式問題組合せ: 局所寄与へ分解して集計順を交換する
技能・出典
主題: 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。既習技能: 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。主タグ: 組合せ係数・数え上げ / 補助タグ: 寄与の数え上げと順序交換
- ABC262 E「Red and Blue Graph」 公式問題組合せ: 法上の四則演算・高速累乗・逆元
技能・出典
主題: 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。)。主タグ: 組合せ係数・数え上げ / 補助タグ: 法上の四則演算・高速累乗・逆元
- ABC266 G「Yet Another RGB Sequence」 公式問題
- ABC226 F「Score of Permutations」 公式問題
技能・出典
主題: 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。)。主タグ: 組合せ係数・数え上げ / 補助タグ: 有界全列挙・有限case分解、法上の四則演算・高速累乗・逆元
- ABC243 F「Lottery」 公式問題組合せ: 法上の四則演算・高速累乗・逆元
技能・出典
主題: 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。)。主タグ: 組合せ係数・数え上げ / 補助タグ: 法上の四則演算・高速累乗・逆元
- ABC276 G「Count Sequences」 公式問題
- ABC290 F「Maximum Diameter」 公式問題
- ABC463 G「Random Walk Distance」 公式問題
技能・出典
主題: 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / Moの順序で区間問い合わせの差分を更新する(区間問い合わせの順序と追加・削除操作を設計し、端点移動の総量を評価できる。)。主タグ: 組合せ係数・数え上げ / 補助タグ: Mo's algorithmによるオフライン区間問い合わせ、法上の四則演算・高速累乗・逆元
- ABC240 G「Teleporting Takahashi」 公式問題組合せ: 幾何の基本判定と座標変換
技能・出典
主題: 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。既習技能: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: 組合せ係数・数え上げ / 補助タグ: 幾何の基本判定・配置・座標変換
- ABC267 G「Increasing K Times」 公式問題
- ABC278 Ex「make 1」 公式問題
技能・出典
主題: 組合せ係数と対称性で数える(生成ベクトルのspan条件をrank別の部分空間数へ変換し、有限体上のGaussian binomial係数で各rankの寄与を数えられる。)。既習技能: 組合せ係数と対称性で数える(冪基底と下降階乗基底の係数をStirling数で変換し、目的のrank別計数列を構成できる。) / NTT・FFTで畳み込みと相互相関を求める(係数積和または反転列との相互相関を多項式積へ変換し、NTT・FFTで必要な係数範囲を計算できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 有限体部分空間のrank別計数 / 補助タグ: 組合せ係数・数え上げ、畳み込み・相互相関、Stirling変換と階乗基底変換
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC214 G「Three Permutations」 公式問題
技能・出典
主題: 包除・Möbius反転で重複を補正する(条件集合の重なり構造を特定し、包除またはMöbius反転の符号と範囲を正しく設定できる。)。既習技能: 組合せを生成関数へ符号化する(組合せの合成を生成関数の積・逆数・畳み込みに符号化できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 集合上の包除原理 / 補助タグ: 組合せ係数・数え上げ、生成関数による組合せ構造の符号化
- ABC215 G「Colorful Candies 2」 公式問題
技能・出典
主題: 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 寄与の数え上げと順序交換 / 補助タグ: 組合せ係数・数え上げ、法上の四則演算・高速累乗・逆元
- ABC216 H「Random Robots」 公式問題主題: 行列式による数え上げ
技能・出典
主題: 行列式による数え上げ(DAG上の経路数行列を作り、交差する経路族の符号反転と端点対応の条件から、LGVで頂点非共有経路族を数えられる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 部分集合・bitmask状態DP(bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 行列式による数え上げ / 補助タグ: 組合せ係数・数え上げ、法上の四則演算・高速累乗・逆元、部分集合・bitmask状態DP
- ABC217 F「Make Pair」 公式問題主題: 区間合成・領域分割DP
技能・出典
主題: 区間合成・領域分割DP(区間や長方形の分割点を列挙し、独立な小領域の答えを合成して領域サイズ順に計算できる。)。既習技能: 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 区間合成・領域分割DP / 補助タグ: 組合せ係数・数え上げ
- ABC225 H「Social Distance 2」 公式問題主題: 組合せを生成関数へ符号化する
技能・出典
主題: 組合せを生成関数へ符号化する(組合せの合成を生成関数の積・逆数・畳み込みに符号化できる。)。追加で学ぶ技能: NTT・FFTで畳み込みと相互相関を求める(係数積和または反転列との相互相関を多項式積へ変換し、NTT・FFTで必要な係数範囲を計算できる。)。既習技能: 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 畳み込み・相互相関、生成関数による組合せ構造の符号化 / 補助タグ: 組合せ係数・数え上げ
- ABC235 G「Gardens」 公式問題
技能・出典
主題: 包除・Möbius反転で重複を補正する(条件集合の重なり構造を特定し、包除またはMöbius反転の符号と範囲を正しく設定できる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。) / DP遷移を因数分解・集約して加速する(隣接する出力の遷移式を比較し、共通項の消去と出入りする項から定数時間更新を導ける。)。 F_A(i)=Σ_{k≤A}C(i,k)を毎回足し直さず、Pascalの式からF_A(i+1)=2F_A(i)−C(i,A)とする。三色分を同時更新して包除の各項を定数時間で計算する。主タグ: 集合上の包除原理 / 補助タグ: 組合せ係数・数え上げ、DP遷移の集約・高速化、法上の四則演算・高速累乗・逆元
- ABC238 Ex「Removing People」 公式問題主題: 時間を逆向きにして未来依存を消す
技能・出典
主題: 時間を逆向きにして未来依存を消す(時間依存を逆走査・逆操作・last-write時刻で単調または静的にし、元の時点へ答えを戻せる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 区間合成・領域分割DP(区間や長方形の分割点を列挙し、独立な小領域の答えを合成して領域サイズ順に計算できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。) / 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。主タグ: 逆向きのオフライン処理 / 補助タグ: 組合せ係数・数え上げ、寄与の数え上げと順序交換、区間合成・領域分割DP、法上の四則演算・高速累乗・逆元
- ABC242 Ex「Random Painting」 公式問題主題: 確率過程・期待値DP
技能・出典
主題: 確率過程・期待値DP(状態から先の期待費用・期待回数を定義し、一歩分の費用と未来の期待値を分け、自己ループを移項した方程式を解ける。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 列・subsequence DP(列の順序を保つ状態と、選ぶ・選ばない遷移を設計できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 確率・期待値DP / 補助タグ: 組合せ係数・数え上げ、法上の四則演算・高速累乗・逆元、列・subsequence DP
- ABC242 F「Black and White Rooks」 公式問題
技能・出典
主題: 包除・Möbius反転で重複を補正する(条件集合の重なり構造を特定し、包除またはMöbius反転の符号と範囲を正しく設定できる。)。既習技能: 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 集合上の包除原理 / 補助タグ: 組合せ係数・数え上げ
- ABC249 Ex「Dye Color」 公式問題
技能・出典
主題: 期待値の頻度圧縮と加法的ポテンシャル(対称な確率過程の期待費用を頻度別関数の和へ分離し、自己ループを含む一段方程式と終端の較正から吸収までの期待費用を求められる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。) / 確率過程・期待値DP(状態から先の期待費用・期待回数を定義し、一歩分の費用と未来の期待値を分け、自己ループを移項した方程式を解ける。)。主タグ: 期待値の頻度圧縮と加法的ポテンシャル / 補助タグ: 組合せ係数・数え上げ、法上の四則演算・高速累乗・逆元、確率・期待値DP
- ABC251 Ex「Fill Triangle」 公式問題
技能・出典
主題: 標数pのFrobenius恒等式による反復高速化(標数pで中間の二項係数が消える恒等式 (1+x)^(p^t)=1+x^(p^t) をシフト演算へ適用し、隣接和反復をpの冪回ずつ飛ばす。圧縮列では各段のrun数の増加も評価する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。) / 端点更新型のrun分割管理(互いに素な同値区間を左端順setで持ち、境界split・局所merge・range eraseでrun構造を動的管理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 標数pのFrobenius恒等式による反復高速化 / 補助タグ: 組合せ係数・数え上げ、ordered interval partition・ODT
- ABC256 F「Cumulative Cumulative Cumulative Sum」 公式問題
技能・出典
主題: 反転数・重み付き接頭辞統計をFenwick Treeで保つ(処理済み値の頻度から反転数を数えるか、必要な添字付き接頭辞統計を導き、Fenwick Treeの線形結合で式を評価できる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: Fenwick Tree・反転数・重み付き接頭辞統計 / 補助タグ: 組合せ係数・数え上げ、法上の四則演算・高速累乗・逆元
- ABC256 G「Black and White Stones」 公式問題主題: 固定線形遷移を巨大回数進める
技能・出典
主題: 固定線形遷移を巨大回数進める(固定線形遷移を行列または漸化式にし、巨大回数後の値を求められる。)。既習技能: 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 線形遷移・行列累乗 / 補助タグ: 組合せ係数・数え上げ
- ABC259 Ex「Yet Another Path Counting」 公式問題主題: 平方根・閾値による軽重分類
技能・出典
主題: 平方根・閾値による軽重分類(頻度・次数・更新回数を閾値でheavy/lightに分け、両側の計算量を均衡させる。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: グリッド・多次元表の局所DPを設計する(グリッドまたは多次元表の依存方向と境界状態を定め、計算済みの局所近傍からDAG順に全状態を更新できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 平方根・閾値による軽重分類 / 補助タグ: 組合せ係数・数え上げ、グリッド・多次元表の局所DP
- ABC260 Ex「Colorfulness」 公式問題主題: 組合せを生成関数へ符号化する
技能・出典
主題: 組合せを生成関数へ符号化する(組合せの合成を生成関数の積・逆数・畳み込みに符号化できる。)。追加で学ぶ技能: FPS基本演算と多項式の多点評価を行う(定数項の前提と次数打切りを確認し、Newton法を用いたFPSの逆数・対数・指数などを畳み込み計算へ還元できる。)。既習技能: NTT・FFTで畳み込みと相互相関を求める(係数積和または反転列との相互相関を多項式積へ変換し、NTT・FFTで必要な係数範囲を計算できる。) / 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 包除・Möbius反転で重複を補正する(条件集合の重なり構造を特定し、包除またはMöbius反転の符号と範囲を正しく設定できる。) / 再帰分割・分割統治(pivot・上位bit・短い側で部分問題へ再帰分割するか、部分結果をbalancedな積木・remainder tree・CDQで重複なく合成できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 形式的べき級数の基本演算、生成関数による組合せ構造の符号化 / 補助タグ: 組合せ係数・数え上げ、畳み込み・相互相関、集合上の包除原理、法上の四則演算・高速累乗・逆元、再帰分割・分割統治
- ABC272 Ex「Flipping Coins 2」 公式問題主題: 多項式の多点評価・補間
技能・出典
主題: 多項式の多点評価・補間(任意の評価点からproduct treeを構築し、剰余をremainder treeで下ろす不変量とO(M(n) log n)の計算量を説明できる。)。追加で学ぶ技能: 組合せを生成関数へ符号化する(組合せの合成を生成関数の積・逆数・畳み込みに符号化できる。)。既習技能: NTT・FFTで畳み込みと相互相関を求める(係数積和または反転列との相互相関を多項式積へ変換し、NTT・FFTで必要な係数範囲を計算できる。) / 包除・Möbius反転で重複を補正する(条件集合の重なり構造を特定し、包除またはMöbius反転の符号と範囲を正しく設定できる。) / 再帰分割・分割統治(pivot・上位bit・短い側で部分問題へ再帰分割するか、部分結果をbalancedな積木・remainder tree・CDQで重複なく合成できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 生成関数による組合せ構造の符号化、多項式の多点評価・補間 / 補助タグ: 組合せ係数・数え上げ、畳み込み・相互相関、集合上の包除原理、再帰分割・分割統治
- ABC273 G「Row Column Sums 2」 公式問題主題: 最小十分状態からDPを設計する
技能・出典
主題: 最小十分状態からDPを設計する(採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。)。既習技能: 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: DPの最小十分状態 / 補助タグ: 組合せ係数・数え上げ
- ABC279 Ex「Sum of Prod of Min」 公式問題主題: 母関数方程式・高度な係数抽出
技能・出典
主題: 母関数方程式・高度な係数抽出(Eulerの五角数定理により∏(1−x^i)を符号付きの疎な係数列へ展開し、必要次数までのO(√N)項で係数抽出できる。)。既習技能: 組合せ係数と対称性で数える(素数pのもとでn,kをp進展開し、Lucasの定理 C(n,k)=∏C(n_i,k_i) mod pで、n≥pでも階乗の零除算を避けて計算できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 母関数方程式・高度な係数抽出 / 補助タグ: 組合せ係数・数え上げ
- ABC281 G「Farthest City」 公式問題主題: 最小十分状態からDPを設計する
技能・出典
主題: 最小十分状態からDPを設計する(採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。)。既習技能: 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: DPの最小十分状態 / 補助タグ: 組合せ係数・数え上げ
- ABC284 Ex「Count Unlabeled Graphs」 公式問題主題: 群作用・軌道数え上げ
技能・出典
主題: 群作用・軌道数え上げ(群作用の固定点数を群要素のcycle typeごとに数え、BurnsideまたはPólyaの平均でorbit数を求められる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 包除・Möbius反転で重複を補正する(条件集合の重なり構造を特定し、包除またはMöbius反転の符号と範囲を正しく設定できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 群作用・軌道数え上げ / 補助タグ: 組合せ係数・数え上げ、集合上の包除原理、法上の四則演算・高速累乗・逆元
- ABC284 G「Only Once」 公式問題
技能・出典
主題: 関数グラフのcycle・tree分解(後続が一意なグラフをcycleと流入木へ分け、各頂点が属する構造を特定できる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。) / 同値な状態を正規化する(対称操作で同値な状態の標準形と不変量を選べる。)。主タグ: 関数グラフのcycle・tree分解 / 補助タグ: 組合せ係数・数え上げ、法上の四則演算・高速累乗・逆元、状態・配置の正規化
- ABC285 Ex「Avoid Square Number」 公式問題
技能・出典
主題: 包除・Möbius反転で重複を補正する(条件集合の重なり構造を特定し、包除またはMöbius反転の符号と範囲を正しく設定できる。)。既習技能: 素因数分解と約数構造(整数の条件を素因数ごとの指数または約数格子上の条件に分解できる。) / 組合せを生成関数へ符号化する(組合せの合成を生成関数の積・逆数・畳み込みに符号化できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 集合上の包除原理 / 補助タグ: 組合せ係数・数え上げ、生成関数による組合せ構造の符号化、素因数・約数分解
- ABC288 Ex「A Nameless Counting Problem」 公式問題主題: 上限制約付き桁DP
技能・出典
主題: 上限制約付き桁DP(数値上限とのtight・先頭ゼロ・剰余・digit maskなどを接頭辞ごとに更新し、条件を満たす数の個数または値の総和を求められる。)。既習技能: 包除・Möbius反転で重複を補正する(条件集合の重なり構造を特定し、包除またはMöbius反転の符号と範囲を正しく設定できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 上限制約付き桁DP / 補助タグ: 組合せ係数・数え上げ、集合上の包除原理
- ABC289 Ex「Trio」 公式問題
技能・出典
主題: FPS基本演算と多項式の多点評価を行う(定数項の前提と次数打切りを確認し、Newton法を用いたFPSの逆数・対数・指数などを畳み込み計算へ還元できる。)。追加で学ぶ技能: NTT・FFTで畳み込みと相互相関を求める(係数積和または反転列との相互相関を多項式積へ変換し、NTT・FFTで必要な係数範囲を計算できる。) / 組合せを生成関数へ符号化する(組合せの合成を生成関数の積・逆数・畳み込みに符号化できる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 畳み込み・相互相関、形式的べき級数の基本演算、生成関数による組合せ構造の符号化 / 補助タグ: 組合せ係数・数え上げ、法上の四則演算・高速累乗・逆元
- ABC295 E「Kth Number」 公式問題
技能・出典
主題: 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 寄与の数え上げと順序交換 / 補助タグ: 組合せ係数・数え上げ、法上の四則演算・高速累乗・逆元
- ABC297 F「Minimum Bounding Box 2」 公式問題
技能・出典
主題: 包除・Möbius反転で重複を補正する(条件集合の重なり構造を特定し、包除またはMöbius反転の符号と範囲を正しく設定できる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。) / 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。主タグ: 集合上の包除原理 / 補助タグ: 組合せ係数・数え上げ、寄与の数え上げと順序交換、法上の四則演算・高速累乗・逆元
- ABC303 Ex「Constrained Tree Degree」 公式問題
技能・出典
主題: Prüfer code・次数制約付きlabel木(Prüfer列とlabel付き木の全単射、および各labelの出現回数=次数-1を使って次数制約を係数条件へ変換できる。)。既習技能: NTT・FFTで畳み込みと相互相関を求める(係数積和または反転列との相互相関を多項式積へ変換し、NTT・FFTで必要な係数範囲を計算できる。) / 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 組合せを生成関数へ符号化する(組合せの合成を生成関数の積・逆数・畳み込みに符号化できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: Prüfer code・次数制約付きlabel木 / 補助タグ: 組合せ係数・数え上げ、畳み込み・相互相関、生成関数による組合せ構造の符号化、法上の四則演算・高速累乗・逆元
- ABC309 G「Ban Permutation」 公式問題
技能・出典
主題: 包除・Möbius反転で重複を補正する(条件集合の重なり構造を特定し、包除またはMöbius反転の符号と範囲を正しく設定できる。)。既習技能: frontier/profile DP・境界状態圧縮(未処理領域へ影響する境界上の色・使用済みフラグ・接続partitionだけを残し、窓外の情報を忘れられることを証明して幅指数のprofile DPを設計できる。) / 部分集合・bitmask状態DP(bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 集合上の包除原理 / 補助タグ: 組合せ係数・数え上げ、frontier/profile DP・境界状態圧縮、部分集合・bitmask状態DP
- ABC313 Ex「Group Photo」 公式問題主題: 最小十分状態からDPを設計する
技能・出典
主題: 最小十分状態からDPを設計する(採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。)。既習技能: 二部matching・Hall・Kőnig(二部割当が可能であることを近傍集合の大きさに関するHall条件で特徴付け、必要ならmin-cut条件と対応させられる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: DPの最小十分状態 / 補助タグ: 二部matching・Hall・Kőnig、組合せ係数・数え上げ
- ABC321 G「Electric Circuit」 公式問題
技能・出典
主題: label付き連結成分分解・exponential formula(最小labelを含む成分を一意に切り出し、全構造とconnected構造の関係をsubset DPまたは指数型母関数で解ける。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 部分集合・bitmask状態DP(bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。) / 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。主タグ: label付き連結成分分解・exponential formula / 補助タグ: 組合せ係数・数え上げ、寄与の数え上げと順序交換、法上の四則演算・高速累乗・逆元、部分集合・bitmask状態DP
- ABC327 G「Many Good Tuple Problems」 公式問題
技能・出典
主題: label付き連結成分分解・exponential formula(最小labelを含む成分を一意に切り出し、全構造とconnected構造の関係をsubset DPまたは指数型母関数で解ける。)。既習技能: 二部彩色と成分構造を扱う(連結二部グラフの二つの彩色が部の交換だけで対応することを使い、彩色付きの計数から同じグラフの重複を補正できる。) / 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 包除・Möbius反転で重複を補正する(条件集合の重なり構造を特定し、包除またはMöbius反転の符号と範囲を正しく設定できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: label付き連結成分分解・exponential formula / 補助タグ: 二部グラフの彩色と成分構造、組合せ係数・数え上げ、集合上の包除原理、法上の四則演算・高速累乗・逆元
- ABC336 G「16 Integers」 公式問題
技能・出典
主題: BEST定理によるEuler circuit数え上げ(有向Euler graphのcircuit数をrooted arborescenceの行列式と各頂点の出辺順列へ分解して数える。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: Euler trail・circuit(無向graphでは辺を持つ部分の連結性と奇数次数頂点数が0または2であることを調べ、有向graphでは辺を持つ部分の弱連結性と入次数・出次数の差(trailなら始点+1、終点−1、他0、circuitなら全頂点0)を調べ、全辺を一度ずつ使うtrail・circuitの存在を判定できる。) / 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 行列式による数え上げ(辺重みからLaplacianを構成し、根の行列余因子を全域木の重み付き個数へ対応させられる。有向木の向きと自己ループの扱いを説明できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: BEST定理によるEuler circuit数え上げ / 補助タグ: 組合せ係数・数え上げ、行列式による数え上げ、Euler trail・circuit、法上の四則演算・高速累乗・逆元
- ABC345 G「Sugoroku 5」 公式問題主題: 組合せを生成関数へ符号化する
技能・出典
主題: 組合せを生成関数へ符号化する(組合せの合成を生成関数の積・逆数・畳み込みに符号化できる。)。追加で学ぶ技能: NTT・FFTで畳み込みと相互相関を求める(係数積和または反転列との相互相関を多項式積へ変換し、NTT・FFTで必要な係数範囲を計算できる。)。既習技能: 平方根・閾値による軽重分類(頻度・次数・更新回数を閾値でheavy/lightに分け、両側の計算量を均衡させる。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 再帰分割・分割統治(pivot・上位bit・短い側で部分問題へ再帰分割するか、部分結果をbalancedな積木・remainder tree・CDQで重複なく合成できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 畳み込み・相互相関、生成関数による組合せ構造の符号化 / 補助タグ: 組合せ係数・数え上げ、法上の四則演算・高速累乗・逆元、再帰分割・分割統治、平方根・閾値による軽重分類
- ABC352 G「Socks 3」 公式問題主題: 組合せを生成関数へ符号化する
技能・出典
主題: 組合せを生成関数へ符号化する(組合せの合成を生成関数の積・逆数・畳み込みに符号化できる。)。追加で学ぶ技能: NTT・FFTで畳み込みと相互相関を求める(係数積和または反転列との相互相関を多項式積へ変換し、NTT・FFTで必要な係数範囲を計算できる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 再帰分割・分割統治(pivot・上位bit・短い側で部分問題へ再帰分割するか、部分結果をbalancedな積木・remainder tree・CDQで重複なく合成できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。) / 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。主タグ: 畳み込み・相互相関、生成関数による組合せ構造の符号化 / 補助タグ: 組合せ係数・数え上げ、寄与の数え上げと順序交換、法上の四則演算・高速累乗・逆元、再帰分割・分割統治
- ABC357 G「Stair-like Grid」 公式問題
技能・出典
主題: 包除・Möbius反転で重複を補正する(条件集合の重なり構造を特定し、包除またはMöbius反転の符号と範囲を正しく設定できる。)。追加で学ぶ技能: Relaxed・online convolution(係数が順に確定する因果的畳み込みをblock分割し、確定済みblock間だけをNTTでまとめて更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 再帰分割・分割統治(pivot・上位bit・短い側で部分問題へ再帰分割するか、部分結果をbalancedな積木・remainder tree・CDQで重複なく合成できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 集合上の包除原理、Relaxed・online convolution / 補助タグ: 組合せ係数・数え上げ、再帰分割・分割統治
- ABC386 G「Many MST」 公式問題
技能・出典
主題: label付き連結成分分解・exponential formula(最小labelを含む成分を一意に切り出し、全構造とconnected構造の関係をsubset DPまたは指数型母関数で解ける。)。追加で学ぶ技能: 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。既習技能: 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 寄与の数え上げと順序交換、label付き連結成分分解・exponential formula / 補助タグ: 組合せ係数・数え上げ
- ABC389 G「Odd Even Graph」 公式問題主題: 最小十分状態からDPを設計する
技能・出典
主題: 最小十分状態からDPを設計する(採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。)。既習技能: 組合せを生成関数へ符号化する(組合せの合成を生成関数の積・逆数・畳み込みに符号化できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: DPの最小十分状態 / 補助タグ: 組合せ係数・数え上げ、生成関数による組合せ構造の符号化
- ABC390 G「Permutation Concatenation」 公式問題主題: 組合せを生成関数へ符号化する
技能・出典
主題: 組合せを生成関数へ符号化する(組合せの合成を生成関数の積・逆数・畳み込みに符号化できる。)。追加で学ぶ技能: NTT・FFTで畳み込みと相互相関を求める(係数積和または反転列との相互相関を多項式積へ変換し、NTT・FFTで必要な係数範囲を計算できる。)。既習技能: 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。) / 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。主タグ: 畳み込み・相互相関、生成関数による組合せ構造の符号化 / 補助タグ: 組合せ係数・数え上げ、寄与の数え上げと順序交換
- ABC392 G「Fine Triplets」 公式問題
技能・出典
主題: NTT・FFTで畳み込みと相互相関を求める(係数積和または反転列との相互相関を多項式積へ変換し、NTT・FFTで必要な係数範囲を計算できる。)。追加で学ぶ技能: 組合せを生成関数へ符号化する(組合せの合成を生成関数の積・逆数・畳み込みに符号化できる。)。既習技能: 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 畳み込み・相互相関、生成関数による組合せ構造の符号化 / 補助タグ: 組合せ係数・数え上げ
- ABC405 G「Range Shuffle Query」 公式問題
技能・出典
主題: Moの順序で区間問い合わせの差分を更新する(区間問い合わせの順序と追加・削除操作を設計し、端点移動の総量を評価できる。)。既習技能: 値軸のbucket分割と区間集約(値軸をblockへ分け、点更新で要約を差分修正し、完全blockと端数からprefixの和・積を取得できる。更新回数とquery回数に応じてblock幅を選べる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。) / 可逆な非零剰余と剰余 0 因子を含む法上の動的積(法 m 上の積で一因子を差し替えるとき、取り得る因子のうち非零剰余がすべて可逆かを確認し、剰余 0 の因子数と可逆な非零剰余因子の積を分離して、可逆な旧因子を逆元で除き新因子を掛けて更新後の積を復元できる。)。主タグ: Mo's algorithmによるオフライン区間問い合わせ / 補助タグ: 組合せ係数・数え上げ、法上の動的積・剰余 0 因子の分離、値軸のbucket分割と区間集約
- ABC409 G「Accumulation of Wealth」 公式問題
技能・出典
主題: NTT・FFTで畳み込みと相互相関を求める(係数積和または反転列との相互相関を多項式積へ変換し、NTT・FFTで必要な係数範囲を計算できる。)。追加で学ぶ技能: 組合せを生成関数へ符号化する(組合せの合成を生成関数の積・逆数・畳み込みに符号化できる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。) / 確率過程・期待値DP(状態から先の期待費用・期待回数を定義し、一歩分の費用と未来の期待値を分け、自己ループを移項した方程式を解ける。)。主タグ: 畳み込み・相互相関、生成関数による組合せ構造の符号化 / 補助タグ: 組合せ係数・数え上げ、法上の四則演算・高速累乗・逆元、確率・期待値DP
- ABC422 G「Balls and Boxes」 公式問題主題: 組合せを生成関数へ符号化する
技能・出典
主題: 組合せを生成関数へ符号化する(組合せの合成を生成関数の積・逆数・畳み込みに符号化できる。)。追加で学ぶ技能: NTT・FFTで畳み込みと相互相関を求める(係数積和または反転列との相互相関を多項式積へ変換し、NTT・FFTで必要な係数範囲を計算できる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 畳み込み・相互相関、生成関数による組合せ構造の符号化 / 補助タグ: 組合せ係数・数え上げ、法上の四則演算・高速累乗・逆元
- ABC432 G「Sum of Binom(A, B)」 公式問題
技能・出典
主題: NTT・FFTで畳み込みと相互相関を求める(係数積和または反転列との相互相関を多項式積へ変換し、NTT・FFTで必要な係数範囲を計算できる。)。追加で学ぶ技能: 組合せを生成関数へ符号化する(組合せの合成を生成関数の積・逆数・畳み込みに符号化できる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 畳み込み・相互相関、生成関数による組合せ構造の符号化 / 補助タグ: 組合せ係数・数え上げ、法上の四則演算・高速累乗・逆元
- ABC453 E「Team Division」 公式問題
技能・出典
主題: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。)。既習技能: 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: event・値順のオフライン走査 / 補助タグ: 組合せ係数・数え上げ
- ABC456 G「Count Holidays」 公式問題
技能・出典
主題: 包除・Möbius反転で重複を補正する(条件集合の重なり構造を特定し、包除またはMöbius反転の符号と範囲を正しく設定できる。)。既習技能: 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。) / 可逆な非零剰余と剰余 0 因子を含む法上の動的積(法 m 上の積で一因子を差し替えるとき、取り得る因子のうち非零剰余がすべて可逆かを確認し、剰余 0 の因子数と可逆な非零剰余因子の積を分離して、可逆な旧因子を逆元で除き新因子を掛けて更新後の積を復元できる。)。主タグ: 集合上の包除原理 / 補助タグ: 組合せ係数・数え上げ、法上の動的積・剰余 0 因子の分離
- ABC459 E「Select from Subtrees」 公式問題主題: 根付き木DP・部分木集約
技能・出典
主題: 根付き木DP・部分木集約(根付き木で子側の状態を合成し、部分木または木全体の値を求められる。)。既習技能: 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 根付き木DP・部分木集約 / 補助タグ: 組合せ係数・数え上げ
- ABC463 F「Senshuraku」 公式問題主題: 同値な状態を正規化する
技能・出典
主題: 同値な状態を正規化する(対称操作で同値な状態の標準形と不変量を選べる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 状態・配置の正規化 / 補助タグ: 組合せ係数・数え上げ、法上の四則演算・高速累乗・逆元
- ABC464 F「Random Vault Heist」 公式問題
技能・出典
主題: meet-in-the-middle・半分全列挙(探索空間を独立に列挙できる二集合へ分け、両側の結果を照合・合成できる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。) / 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。主タグ: meet-in-the-middle・半分全列挙 / 補助タグ: 組合せ係数・数え上げ、寄与の数え上げと順序交換、法上の四則演算・高速累乗・逆元
前提・学習成果・出典
習得対象の目安: 水色(1200–1599)。通常・Gaussian二項係数、Stirling変換、法上の階乗を使い、rank別計数を基底変換する。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 組合せ・多項式・線形代数。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-combinatorial-coefficients
習得する技能
- 冪基底と下降階乗基底の係数をStirling数で変換し、目的のrank別計数列を構成できる。
- 素数pのもとでn,kをp進展開し、Lucasの定理 C(n,k)=∏C(n_i,k_i) mod pで、n≥pでも階乗の零除算を避けて計算できる。
- 生成ベクトルのspan条件をrank別の部分空間数へ変換し、有限体上のGaussian binomial係数で各rankの寄与を数えられる。
- 選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: なし。
このUnitを直接前提とする単元: 組合せを生成関数へ符号化する、factorial convolutionによる多項式Taylor shift、Prüfer code・次数制約付きlabel木、鏡像法・reflection principle。
選び方を通常・Gaussian二項係数で整理し、必要ならStirling変換でrank別計数を基底変換する。
このUnitでは扱わないもの
- 重なりを交互加減する包除・Möbius反転。