Doubt in Counting Necklaces CSES problem

Правка en1, от Surge226, 2024-09-01 17:13:24

Hello everyone, I am trying to solve Required Substring problem from CSES.

I thought about a combinatorial solution for the problem. My idea was that for every $$$i < n$$$

  • if $$$i$$$ does not divide $$$n$$$, then there would be total $$$n$$$ arrangements which would be similar, so we would have to count $$$ways = \frac{\text{# of arrangements}}{n}$$$ in it, for ex, in sample test case, $$$n=4, m=3$$$, arrangement, {$$$1,1,1,2$$$}, {$$$1,1,2,1$$$}, {$$$1,2,1,1$$$}, {$$$2,1,1,1$$$} would be considered similar
  • if $$$i$$$ divides $$$n$$$, then there would be total $$$i$$$ arrangements which would be similar, so we would have to count $$$ways = \frac{\text{# of arrangements}}{i}$$$ in it, for ex, in sample test case, $$$n=4, m=3$$$, arrangement, {$$$1,2,1,2$$$}, {$$$2,1,2,1$$$} would be considered similar

So, I am iterating from $$$0$$$ to $$$n-1$$$, and if current period is prime and it divides total number of pearls $$$n$$$, then we can subtract the number of arrangements which it can form, from total number of arrangements and add the number of ways to the answer. We should also check whether, current period is prime because the period for $$$4$$$ would be same as $$$2$$$

My Code

Surprisingly, my code worked for smaller test cases, but it is giving wrong answer for large test cases. I checked the modular operations also and the factorial and prime conditions, but cannot figure out the issue. If anyone can help me out in this, I would highly appreciate it.

Thanks

Теги cses, combinatorics

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Surge226 2024-09-01 17:13:24 1962 Initial revision (published)