Number of partitions on a circle

Revision en3, by cuom1999, 2020-11-19 07:22:24

We usually see problems like: Given an array $a_1, a_2, ..., a_n$. How many ways to partition the array into continuous groups in which each group satisfies a condition (e.g sum not exceeding a number, ...)? This kind of problem is usually done in linear or log-linear time with dynamic programming and prefix sum.

What about changing the statement to a circular array? Formally, given a circular array $a_1, a_2, ..., a_n$. How many ways to partition the circle into continuous groups in which each group satisfies a condition? Two ways are different if there are two indices belonging to the same group in one way, but different groups in the other way.

How to solve this problem in sub-quadratic time in general? I find even the simplest conditions like the below are quite hard.

a) Each group has sum $\leq M$, with a given $M$.

b) Each group has $gcd > 1$.

...

Solution for problem a or b are appreciated.

#### History

Revisions

Rev. Lang. By When Δ Comment
en3 cuom1999 2020-11-19 07:22:24 17 Change to sub quadratic
en2 cuom1999 2020-11-18 23:13:27 48 Tiny change: '1$.\n\n...' -> '1$.\n\n...\n\nSolution for problem a or b are appreciated.'
en1 cuom1999 2020-11-18 06:51:48 911 Initial revision (published)