考察
隣り合う値が等しい列を包除で打ち消す。等しい隣接項の境界を選んで結合すると、同じ値を並べた部品へ分解でき、部品を自由に並べる母関数が使える。さらに、元の列の長さを別の変数の指数に記録し、微分で長さの総和を取り出す。
等値な境界を選び、不適な列を相殺する
求めるのは、総和が で、隣り合う値がすべて異なる正整数列の長さの総和である。正整数列の全列挙では、 個の1の間に区切りを置くかどうかを選ぶだけでも 通りある。 では、列を一つずつ作れない。
まず隣接条件を外し、包除原理で不適な列を消すことを考える。正整数列 に対し、値が等しい隣接境界の集合を
とする。列 だけでなく、そこから選んだ境界の部分集合 との組 を数え、その重みを
と定める。 の指数は要素の総和、 の指数は元の列の長さであり、どの境界を選んでも変わらない。
列 を固定し、 とすると、全部分集合の符号和は
となる。等値な境界が一つでもあれば0、なければ空集合を選ぶ1通りだけが残る。したがって、この符号付きの和は合法な列だけを1回ずつ数える。
選んだ境界だけを結び、部品を自由に並べる
組 を扱いやすくするため、 に含まれる境界だけを結合する。一つの部品は、ある値 が 個並んだものになる。内部の 境界を選んでいるので、その重みは
である。この部品は、同じ値が続く最大区間とは限らない。 等値な境界でも選ばなければ切れたままであり、隣り合う二部品の値が同じでもよい。
例えば、総和4の不適な列 には、等値な境界が最初の1箇所だけある。
- 境界を選ばないと、部品列は となり、重みは 。
- 最初の境界を選ぶと、部品列は となり、重みは 。
部品数は3から2へ変わるが、どちらも元の長さ3を記録するため、ちょうど相殺される。ここで同じ値の部品の隣接を禁じると、前者を落としてしまい、包除が崩れる。
逆に、こうした部品を任意の順序で並べれば、展開して元の列 を復元し、部品内部の境界をすべて選ぶことで も一意に復元できる。よって、組 と部品列は一対一に対応する。
一つの部品の重みをすべて足した母関数を と置く。値 を固定すると、長さ に関する交代符号の等比級数になるので、
である。部品数が の列は で表せる。空列も含めた部品列の母関数を とすれば、
となる。どの部品も総和が正なので であり、 以下には高々 個の部品しか寄与しない。形式冪級数としてこの和を扱え、解析的な収束は不要である。先ほどの相殺により、 は、総和 ・長さ の合法な列の個数に等しい。
長さを記録する変数を微分する
列数を長さ別に求めてから足す必要はない。 を微分して を代入すれば になるため、各列をその長さだけ数えられる。ここで微分するのは、部品数を表す変数ではなく、各部品内の元の要素数まで記録した である。
一変数の級数を
と定義する。 を微分すると、長さの総和の母関数は
となる。従って、答えはこの式の の係数である。
具体的に、 の各項の微分から
を得る。 の次数を固定すれば元の長さも有限なので、微分と の代入は係数ごとに行える。空列の項は1であり、微分への寄与は0になる。
約数ごとの寄与から係数列を作る
残るのは を 次まで作ることである。、 と書くと、部品の重みとその 微分から、 について
となる。微分で掛かるのは元の長さ である。定数項はどちらも 。
長さ の係数配列を0で初期化し、 に対して を走査する。 の位置へ、 が奇数なら に1、 に を足し、偶数ならそれぞれを引く。値 ごとに有理式の逆元を求める必要はない。
例えば に寄与する は であり、、 となる。これらは相殺前の符号付き部品の係数なので、負になってもよい。
最後は、法 上で次の順に計算する。
- を作り、FPSの逆元 を 次まで求める。 なので逆元が存在する。
- NTTによる畳み込みで 、続いて を求める。積のたびに 次まで残す。
- を出力する。
なら、残る合法な列は であり、長さの和は となる。
典型の発動条件
包除付き母関数
局所的な禁止条件を直接守って並べるのが難しいとき、違反箇所の部分集合へ符号を付けて数える。選んだ違反が連続区間を結ぶなら、その区間を一部品として表せないかを考える。部品への分解と元の対象・選択集合との対応を確認してから、部品列の母関数を使う。
marking variableの微分
構造の個数だけでなく、長さや要素数の総和が欲しいときは、その量を補助変数の指数に記録する。微分後に1を代入すると、その量を重みにできる。部品を圧縮した場合も、数えたい元の要素数を指数に保持することが必要である。
形式冪級数逆元
非空の部品を自由に並べる構造から逆数が現れたら、まず定数項が可逆かを調べる。必要次数までの係数列を作れれば、NTTとNewton法で逆元を高速に求められる。
問題固有の要素
禁止条件が「隣接する値の一致」なので、選んだ違反境界を結んだ区間は同じ値の繰り返しになる。値 と長さ だけで部品が定まり、総和は積 になる。このため、部品の係数を約数ごとの寄与として列挙できる。
正当性
部品列を展開し、部品内部の境界を選ぶと、元の正整数列と等値境界の部分集合の組が一意に定まる。逆にその組から選択境界だけを結合すれば同じ部品列へ戻るため、部品列の母関数はすべての組を漏れ・重複なく数える。
一つの列に対する符号和は、等値境界があれば0、なければ1になる。各分割は元の列の総和と長さを同じ指数に保持するので、相殺は長さ別にも成立する。従って、相殺後の母関数の係数は合法な列の個数である。
この母関数を長さの変数で微分して1を代入すると、各合法列の寄与がその長さになる。微分結果は であり、約数寄与で作った係数列と、定数項1の の逆元からその 次係数を求める手順は、要求された長さの総和を返す。
実装上の注意
- 計算はすべて法 上で行い、負の寄与も剰余として正規化する。 とし、 を作るときは定数項だけが1になる。
- 保持するのは 次の 係数である。逆元も積も を法として打ち切る。低次数の係数は高次数の項から影響を受けない。
- NTTでは巡回畳み込みにならないよう、打切り前の積に必要な長さまで0で埋める。上限でも、長さ 同士の積は 係数であり、変換長 で足りる。この長さは法 で扱える。
- 小規模な検算では、不適な列の相殺と長さの重みを別々に確かめる。 の答えは順に となる。
復習の核
- 包除で結ぶのは「選んだ境界」だけ。同じ値の部品の隣接を許すことが、相殺に必要になる。
- 圧縮後も、補助変数の指数は求めたい元の量を保つ。ここでは部品数ではなく、元の列の長さである。
- 二変数の係数表を作る前に、微分と代入で欲しい重みの総和だけを取り出せないか考える。
計算量と制約
時間
約数寄与の二重ループの総反復数は
である。NTTでの畳み込みと、精度を倍増するNewton法でのFPS逆元も 。その後の2回の積まで含め、全体で となる。
空間
係数配列とNTTの作業領域に を使う。長さ別の二変数係数表は保持しない。
制約との対応
公式制約は 、実行時間制限4秒、メモリ制限1024 MiBである。全列挙や二次元の係数表を避け、約数寄与と高速な級数演算を使うことで、この上限に対応する。
出典