Fail to solve ARRAYCOUNT problem due to wrong modeling of the combination

help
,
1

My issue

Mint totalWays = 0;
    for (int n = 1; n <= len ; n++) {
        Mint ways = 1;
        for (auto& [p, cnt] : v) { // p was the prime number, cnt is the number of times that factor present
            ways *= n * power<Mint>(cnt + 1, n - 1) ;
        }
        totalWays += (ways);
    }
    cout << totalWays << cline;

While solving this problem I wasted my whole time on the line

            ways *= n * power<Mint>(cnt + 1, n - 1) ;

When I was modeling the combination, I modeled my requirement like this.

(Select 1 POSITION out of N Where Cnt number of primes can be assigned) AND (For remaining we can assign maximum of cnt + 1 number of prime factor )

which concluded into the formula for 1 prime like

nC1 * (cnt + 1)^(n - 1) ;

Now I know this is incorrect its having duplicate values also but I need help to understand the issue on my modeling,
according to the statement I provided on top, why the formula does not work.

and also then this formula I have provided calculates exactly what ?

and is there any way to solve it alter my problem modeling and solve it differently like I was trying to , instead of going with the trivial (cnt + 1)^n - cnt^n way ?

PLEASE NOTE : I know the correct solution, what I need is some help to understand how wrong was my modeling statement was.

Problem Link: https://www.codechef.com/problems/ARRAYCOUNT
2

Perhaps one way to use your model to arrive at the right count would be as follows: Choose position 1 and assign highest power to it. This can be done in (1+cnt)^{(n-1)} ways. The other distinct ways include the cases where position 1 does not have the highest power. It can be assigned power from 0 to cnt-1. Position 2 can be chosen now to have the highest power. This can be done in cnt \cdot (1+cnt)^{(n-2)}. The cases that aren’t considered yet are to assign both positions 1 and 2 with powers 0 to cnt-1.
Extending the cases all the way till only position n can have the highest power, the total count would be:
\sum_{i=0}^{n-1}{cnt^{i} \cdot (1+cnt)^{(n-1-i)}}
Since the sequence is in GP, the series sum can be computed and it indeed turns out to be (1+cnt)^n - cnt^n.

1 Like
3

Thanks man, you are awesome

1 Like
4

this is because this argument having duplicate values just like what you said, suppose if out of all nC1 we choose 1st array to have factor p^cnt now while we count (cnt+1)^(n-1) happen that 2nd array have also factor p^cnt. Now the second time you count nC1 and choose 2nd array to have factor p^cnt and count (cnt+1)^(n-1) the 1st array also have factor p^cnt you count it double.

nothing, just wrong way of thinking

i think you can use inclusion-exclusion, but you will need O(n^2)

1 Like
5

Thanks for sharing your knowledge, learning more