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 sublog-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-linearquadratic 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.
↵
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-
↵
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.
