方針

各絵画のレプリカを受け取るのは、その絵画に描かれた地域のうち最も早く訪れた地域です。したがって、各絵画を長さ \(K\) 以下の連続区間とみなし、各区間をその中で最も早く訪れた地域に割り当てる問題として考えます。

\(K=1\) の場合、各絵画には一つの地域だけが描かれます。したがって訪問順によらず \((C_1,\ldots,C_N)=(1,\ldots,1)\) であり、答えは \(1\) です。

以下では \(K\geq2\) とします。

まず、円環ではなく \(1,2,\ldots,n\) が直線上に並んでいる場合を考えます。長さ \(K\) 以下のすべての連続区間を同様に割り当てたとき、得られる個数列の種類数を \(a_n\) とし、\(a_0=a_1=1\) とします。また、\(n\) 番目の Catalan 数を \(\operatorname{Cat}_n=\frac{1}{n+1}\binom{2n}{n}\) とします。

補題 1. \(n\geq2\) に対して、

\[ a_n=2a_{n-1}+\sum_{j=2}^{\min(K-1,n-1)}\operatorname{Cat}_{j-1}\,a_{n-j} \]

が成り立つ。また、\(n\lt K\) なら \(a_n=\operatorname{Cat}_n\) である。

証明

境界をまたぐ区間を扱うため、直線の左側に $h$ 個のダミー頂点を置いた問題も考えます。ここで $0\leq h\leq K-1$ とします。 ダミー頂点は、すでに切り離した左側の頂点を表すためのものです。ダミー頂点を含む区間も考えますが、その区間に実際の頂点が含まれる場合、ダミー頂点がその区間の割り当て先になることはないものとします。また、実際の $n$ 頂点が受け取る枚数だけを記録します。 この問題で得られる個数列の集合を $L_{n,h}$ とします。$h=0$ が元の直線上の問題です。 次の二つを $n$ に関する帰納法で同時に示します。 - $|L_{n,h}|$ は $h$ によらず $a_n$ である。 - $n\lt K$ なら $a_n=\operatorname{Cat}_n$ である。 $n=0,1$ では明らかです。 $1\leq q\leq\min(K,n)$ の範囲で、頂点 $1$ が頂点 $1,2,\ldots,q$ の中で最も早く訪れられるような $q$ の最大値を $j$ とします。 このとき $1\leq j\leq\min(K,n)$ であり、$j\lt\min(K,n)$ なら頂点 $j+1$ は頂点 $1$ より早く訪れます。 頂点 $1$ が受け取る絵画の枚数は $$ \sum_{q=1}^{j}\min(h+1,K-q+1) $$ です。実際、右端が $q$ である区間について、左端は頂点 $1$ またはその左側のダミー頂点から選べますが、区間の長さは $K$ 以下でなければなりません。この値は $j$ について狭義単調増加なので、個数列の第 $1$ 成分から $j$ を一意に復元できます。 $j=1$ の場合、頂点 $2$ は頂点 $1$ より早く訪れます。そのため、頂点 $1$ を含み頂点 $2$ 以降まで伸びる区間では、頂点 $1$ が割り当て先になることはありません。 そこで頂点 $1$ を削除すると、元からあった $h$ 個のダミー頂点と頂点 $1$ をまとめて、左側に $h+1$ 個のダミー頂点がある問題とみなせます。ただし長さ $K$ の区間より遠い頂点は影響しないため、ダミー頂点の個数は高々 $K-1$ 個だけ覚えれば十分です。 したがって残りは $L_{n-1,\min(K-1,h+1)}$ と同じ問題になり、帰納法の仮定より $a_{n-1}$ 通りです。 次に $j=\min(K,n)$ の場合を考えます。頂点 $1$ を含む長さ $K$ 以下の区間はすべて頂点 $1$ に割り当てられます。そのため頂点 $1$ を削除すると、残りには左側からまたがる区間の影響が残らず、通常の $n-1$ 頂点の直線上の問題になります。よって $a_{n-1}$ 通りです。 最後に $2\leq j\leq\min(K-1,n-1)$ の場合を考えます。 ここで $u\rightarrow v$ は「頂点 $u$ を頂点 $v$ より先に訪れる」ことを表します。この場合、 $$ j+1\rightarrow1\rightarrow\{2,3,\ldots,j\} $$ が成り立ちます。 頂点 $2,\ldots,j$ が受け取る絵画は、この範囲の内部だけに含まれるものです。この部分には $j-1\lt K$ 個の頂点しかないため、帰納法の仮定より $\operatorname{Cat}_{j-1}$ 通りです。 一方、頂点 $j+1,\ldots,n$ を考えます。この部分より左にある頂点を含む区間には必ず頂点 $j+1$ も含まれます。また、頂点 $j+1$ は頂点 $1,\ldots,j$ より早く訪れるため、左側の頂点がその区間の割り当て先になることはありません。 したがって、左側の $h+j$ 個の頂点はすべてダミー頂点として扱えます。残りは $L_{n-j,\min(K-1,h+j)}$ と同じ問題になり、$a_{n-j}$ 通りです。 左右は独立に選べ、さらに $j$ は第 $1$ 成分から一意に復元できます。よって、 $$ a_n=2a_{n-1}+\sum_{j=2}^{\min(K-1,n-1)}\operatorname{Cat}_{j-1}\,a_{n-j} $$ を得ます。この式は $h$ に依存しないため、$|L_{n,h}|=a_n$ も示されました。 さらに $n\lt K$ のとき、帰納法の仮定を代入すると $$ a_n=2\operatorname{Cat}_{n-1}+\sum_{j=2}^{n-1}\operatorname{Cat}_{j-1}\operatorname{Cat}_{n-j}=\operatorname{Cat}_n $$ となります。最後の等号は Catalan 数の漸化式によります。 以上で示されました。

\(H(x)=\sum_{n\geq1}a_nx^{n-1}\) とおくと、補題 1 より

\[ H(x)=\frac1{F(x)},\qquad F(x)=1-2x-\sum_{j=2}^{K-1}\operatorname{Cat}_{j-1}x^j \]

を得ます。

円環への適用

地域 \(i\) を含む長さ \(d\) の区間は \(d\) 個なので、\(C_i\leq1+2+\cdots+K=\frac{K(K+1)}2\) です。等号を満たす地域を「切れ目」と呼びます。

補題 2. 切れ目は少なくとも \(1\) 個存在し、隣り合う切れ目の間には少なくとも \(K-1\) 個の地域が存在する。

証明

全地域の中で最も早く訪れた地域は、それを含むすべての区間がその地域に割り当てられるため、切れ目になります。 また、二つの切れ目の間にある地域が $K-2$ 個以下なら、その二つをともに含む長さ $K$ 以下の区間が存在します。しかし、一つの区間を二つの地域に割り当てることはできないため、矛盾します。

いくつかの切れ目を選び、隣り合う二つの選んだ切れ目の間に \(g\) 個の地域があるとします。この \(g\) 個の地域については直線上の補助問題となるため \(a_g\) 通りであり、補題 2 より \(g\geq K-1\) です。

そこで、一つの切れ目と、その次の切れ目までの \(g\) 個の地域を一つのブロックとみなし、

\[ D(x)=\sum_{g\geq K-1}a_gx^{g+1} \]

とおきます。

\(r\) 個の切れ目を選ぶと円環は \(r\) 個のブロックに分かれます。先頭の切れ目を置く場所が \(N\) 通りあり、同じ選び方を \(r\) 個の切れ目のどこから読んでも同じものになるため、その数は \(\frac Nr[x^N]D(x)^r\) です。

実際に切れ目が \(m\) 個ある個数列は、\(r\) 個の切れ目の選び方によって \(\binom mr\) 回数えられます。ここで \(\sum_{r=1}^{m}(-1)^{r+1}\binom mr=1\) なので、包除原理より

\[ \mathrm{Ans}=\sum_{r\geq1}(-1)^{r+1}\frac Nr[x^N]D(x)^r=N[x^N]\log(1+D(x)) \]

となります。

答えの計算

\(A(x)=\sum_{n\geq0}a_nx^n\) とおくと、\(A(x)=1+xH(x)=1+\frac{x}{F(x)}\) です。

ここで

\[ E(x)=F(x)+x=1-\sum_{j=1}^{K-1}\operatorname{Cat}_{j-1}x^j \]

とおけば、\(A(x)=E(x)/F(x)\) です。

また、補題 1 より \(g\leq K-2\) では \(a_g=\operatorname{Cat}_g\) なので、

\[ D(x)=x\left(A(x)-\sum_{g=0}^{K-2}\operatorname{Cat}_gx^g\right). \]

\(E(x)\) の定義から \(1-E(x)=x\sum_{g=0}^{K-2}\operatorname{Cat}_gx^g\) なので、整理すると

\[ 1+D(x)=\frac{E(x)^2}{F(x)} \]

となります。

したがって、

\[ \mathrm{Ans}=N[x^N]\left(2\log E(x)-\log F(x)\right). \]

さらに \((\log G(x))'=G'(x)/G(x)\) より、

\[ \mathrm{Ans}=[x^{N-1}]\left(2\frac{E'(x)}{E(x)}-\frac{F'(x)}{F(x)}\right) \]

を得ます。

\(E(x)^{-1},F(x)^{-1}\) を FPS の逆元として求めれば、この式を計算できます。

計算量

NTT と Newton 法を用いて \(E(x)^{-1},F(x)^{-1}\) を \(N\) 項まで求めることで、各テストケースを \(O(N\log N)\) 時間、\(O(N)\) 空間で解くことができます。

また、Bostan–Mori 法を用いれば \(O(K\log K\log N)\) 時間、\(O(K)\) 空間で求めることもできます。