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$$$

int allWays = pwr(m, n);
int ans = 0;
for(int i=1;i<n;i++) {
    if(isPrime[i] && n % i == 0 && i <= m) {
        int iLengthPeriod = nPr(factorialArray, m, i);
        allWays = (1ll * allWays - iLengthPeriod + mod) % mod;
        ans = (1ll * ans + (1ll * iLengthPeriod * inverse(i)) % mod) % mod;
    }
}

ans = (1ll * ans + (1ll * allWays * inv(n)) % mod) % mod;
cout << ans << "\n";

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