What is the fastest known solution for the Counting Necklaces problem?
Difference between en1 and en2, changed 34 character(s)
Hello codefoces users.↵

A while ago, I solved CSES problem 2209 ([https://cses.fi/problemset/task/2209](https://cses.fi/problemset/task/2209)) related to combinatorics involving necklaces (https://en.wikipedia.org/wiki/Necklace_(combinatorics)) with a time complexity of O(sqrt(n) + divs(n)
^2 * (divs(n) + log(n))). I believe this complexity can be further reduced to O(sqrt(n) + divs(n) * (2^(nOfPrimes(n)) * log(divs(n)) + log(n))).↵

Upon reading the editorial, I discovered that the official solution utilizes Burnside's Lemma and has a time complexity of O(nlogn). I was unsure if my solution was previously known or not.↵

After conducting some research, I was unable to find a similar solution to mine. Consequently, I considered using this problem with higher constraints in a future contest. However, I am uncertain whether this is a wise decision. Therefore, I have two questions:↵

1. Is there a known solution with a better time complexity for this problem than my approach?↵
2. Would it be advisable to incorporate a classical problem with higher constraints into a contest?↵

Thank you for your assistance.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English danx 2023-10-02 00:13:58 34
en1 English danx 2023-10-01 22:54:02 1164 Initial revision (published)