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.