If we can enumerate the number of schedules (which we will denote by \(F(S,k)\)) with at most \(k\) consecutive holidays, the answers can be found by their differences.

Since consecutive holidays cannot stride over x, we can split \(S\) at x to reduce to problems for strings of just repeated ., and \(F(S,k)\) equals the product of \(F(T_1,k)F(T_2,k)\cdots F(T_l,k)\) defined for the strings \(F(T_1,k)F(T_2,k)\cdots F(T_l,k)\) obtained by splitting \(S\) at xs.

Let \(f(n,k)\) be the value \(F(T,k)\) for the string \(T\) consisting of \(n\) copies of .. If \(k\geq n\), then \(f(n,k)=2^n\). Also, for \(k\lt n\), we can compute \(f(n,k)\) in \(O\left(\frac{n}{k+2}\right)\) time (as described later). Therefore, \(F(S,k)\) can be enumerated for all \(k\) in a total of \(O(N\log N)\) time.

We will introduce two approaches to computing \(f(n,k)\): one using Inclusion-Exclusion Principle, and one using Formal Power Series. Both yields the same result.

Using Inclusion-Exclusion Principle

Let \(g(n,k,m)\) be the number of pairs of “a way to choose \(m\) out of \(n\) days” and “a work schedule such that each of the chosen days is the first day of \((k+1)\) or more consecutive holidays (i.e. is either day \(1\), or the day before is a workday).” By Inclusion-Exclusion Principle, \(f(n,k)=\sum_{m=0}^{n}(-1)^mg(n,k,m)\).

Trivially, \(g(n,k,m)=0\) if \((k+2)m-1\gt n\), so the range of \(m\) for the sum can be set \(0\leq m\leq\frac{n+1}{k+2}\).

We discuss by cases considering whether day \(1\) is chosen or not. The following two correspond one-to-one:

• Choose \(m\) days out of the \(n\) days except for day \(1\), and a work schedule such that each of the chosen days is the first day of \((k+1)\) or more consecutive holidays.
• Place \(m\) blocks of “one workday + \((k+1)\) holidays” freely within day \(1\) through day \(n\), and freely determine the schedule for the other days.
  • There are \(2^{n-(k+2)m}\binom{n-(k+1)m}{m}\) such ways (or \(0\) ways if \(n-(k+2)m\lt 0\)).

The following also corresponds one-to-one:

• Choose \(m\) days out of the \(n\) days except for day \(1\), and a work schedule such that each of the chosen days is the first day of \((k+1)\) or more consecutive holidays.
• Make day \(1\) through day \((k+1)\) holidays; within day \((k+2)\) through day \(n\), place \((m-1)\) blocks of “one workday + \((k+1)\) holidays,” and freely determine the schedule for the other days.
  • There are \(2^{n-(k+2)m+1}\binom{n-(k+1)m}{m-1}\) such ways (or \(0\) ways if \(n-(k+2)m+1\lt 0\)).

Hence, \(g(n,k,m)\) can be computed in \(O(1)\) time (after appropriate precalculation), and \(f(n,k)\) can be found in \(O\left(\frac{n}{k+2}\right)\) time.

Using Formal Power Series

We introduce a FPS (Formal Power Series) based approach.

\(f(n,k)\) represent the number of schedules such that:

• \(0\) to \(k\) holidays, one workday, \(0\) to \(k\) holidays, ……, one workday, \(0\) to \(k\) holidays

This can be represented using an FPS as follows:

\[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.\]

This can be further deformed as:

\[\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}\]

To find the coefficient for the last expression, it is sufficient to consider the range \(i\leq \frac{n}{k+2}\). With \([x^m]\frac{1}{(1-2x)^{i+1}}=2^m\binom{m+i}{m}\), the coefficients for \(x^n\) can be computed in \(O\left(\frac{n}{k+2}\right)\) after precalculating the factorials.