最長の連休が \(k\) 日以下の勤務予定の総数（\(F(S,k)\) とする）を列挙できれば、差分を取ることで元の問題に答えられます。

連休は x を跨ぐことはできないため x で \(S\) を分割することで . のみからなる文字列についての問題に帰着でき、\(F(S,k)\) の値は x で \(S\) を分割してできる文字列 \(T_1,T_2,\dots,T_l\) についての総積 \(F(T_1,k)F(T_2,k)\cdots F(T_l,k)\) に等しいです。

. を \(n\) 個繋げた文字列 \(T\) についての \(F(T,k)\) の値を \(f(n,k)\) とします。 \(k\geq n\) ならば \(f(n,k)=2^n\) です。 また \(k\lt n\) のとき \(f(n,k)\) は \(O\left(\frac{n}{k+2}\right)\) 時間で計算できます（後述します）。 従って累積積などを利用すれば \(F(S,k)\) の \(k\) についての列挙は \(O(N\log N)\) 時間で行えます。

\(f(n,k)\) の計算について、包除原理を用いる方法と形式的冪級数を用いる方法の2通りを紹介します。 どちらでも同じ結果が得られます。

包除原理を用いる

「\(n\) 日のうち \(m\) 日を選ぶ方法」と「選んだ \(m\) 日がいずれも \(k+1\) 日以上の連休の初日（\(1\) 日目であるか前日が勤務日）であるような勤務予定」の組の総数を \(g(n,k,m)\) とします。 包除原理により \(f(n,k)=\sum_{m=0}^{n}(-1)^mg(n,k,m)\) です。

簡単にわかることとして \((k+2)m-1\gt n\) ならば \(g(n,k,m)=0\) であるため、総和の \(m\) の範囲は \(0\leq m\leq\frac{n+1}{k+2}\) としてよいです。

\(1\) 日目を選ぶかどうかで分けて考えます。 以下の二つが一対一で対応しています。

• \(n\) 日のうち \(1\) 日目を含まないように \(m\) 日を選び、それらがいずれも \(k+1\) 日以上の連休の初日であるような勤務予定を選ぶ。
• \(1\) 日目から \(n\) 日目の中に「勤務日 \(1\) 日 + 休日 \(k+1\) 日」を \(m\) 個置き、残りの日を自由に決める。
  • \(2^{n-(k+2)m}\binom{n-(k+1)m}{m}\) 通り（\(n-(k+2)m\lt 0\) なら \(0\) 通り）。

また以下の二つも一対一で対応しています。

• \(n\) 日のうち \(1\) 日目を必ず含むように \(m\) 日を選び、それらがいずれも \(k+1\) 日以上の連休の初日であるような勤務予定を選ぶ。
• \(1\) 日目から \(k+1\) 日目を休日とし、\(k+2\) 日目から \(n\) 日目の中に「勤務日 \(1\) 日 + 休日 \(k+1\) 日」を \(m-1\) 個置き、残りの日を自由に決める。
  • \(2^{n-(k+2)m+1}\binom{n-(k+1)m}{m-1}\) 通り（\(n-(k+2)m+1\lt 0\) なら \(0\) 通り）。

従って \(g(n,k,m)\) は適当な前計算のもとで \(O(1)\) 時間で計算でき、\(f(n,k)\) は \(O\left(\frac{n}{k+2}\right)\) 時間で計算できます。

形式的冪級数を用いる

形式的冪級数 (FPS) を用いて計算します。

\(f(n,k)\) で数えたい勤務予定は以下の形のものです。

• 休日 \(0\) ~ \(k\) 日、勤務日 \(1\) 日、休日 \(0\) ~ \(k\) 日、……、勤務日 \(1\) 日、休日 \(0\) ~ \(k\) 日

FPS を用いれば以下のようにして表現できます。

\[f(n,k)=[x^n]\sum_{i=0}^{\infty}\frac{1-x^{k+1}}{1-x}\left(x\cdot\frac{1-x^{k+1}}{1-x}\right)^i\]

以下のように変形することができます。

\[\begin{aligned} &\phantom{=}\sum_{i=0}^{\infty}\frac{1-x^{k+1}}{1-x}\left(x\cdot\frac{1-x^{k+1}}{1-x}\right)^i\\ &=\frac{1-x^{k+1}}{1-x}\cdot\frac{1}{1-x\cdot\frac{1-x^{k+1}}{1-x}} \\ &=\frac{1-x^{k+1}}{1-2x+x^{k+2}} \\ &=\frac{1-x^{k+1}}{1-2x}\cdot\frac{1}{1+\frac{x^{k+2}}{1-2x}} \\ &=\sum_{i=0}^{\infty}\frac{1-x^{k+1}}{1-2x}\left(-\frac{x^{k+2}}{1-2x}\right)^i \\ &=\sum_{i=0}^{\infty}(-1)^i\frac{x^{(k+2)i}(1-x^{k+1})}{(1-2x)^{i+1}} \end{aligned}\]

最後の式における \(x^n\) の係数を求めるには \(i\leq \frac{n}{k+2}\) の範囲の \(i\) のみ考えればよく、\([x^m]\frac{1}{(1-2x)^{i+1}}=2^m\binom{m+i}{m}\) であることを用いると \(x^n\) の係数は階乗の前計算のもとで \(O\left(\frac{n}{k+2}\right)\) 時間で計算できます。