Count the number of subsequence

This question is from last weeks morkvita… Please help is ther any permutation formula avilable to that… Or some better approach… Or only backtraking is the solution for this

1 Like

Calculate the number of factors of ‘N’ .

Say , it is, ‘x’ .

Now, this relation holds true :-
a(i) = i * a(i-1) + (i-1) * a(i-2), a(0) = 1, a(1) = 1.
(I’ll explain how I reached here later).
Now, a(x) is your answer.
Also, the maximum value of ‘x’ will be 346(square-root of 120000).
So , you can just run a loop, calculate a(x) from the above relation and the problem is solved :slight_smile:

Harder version of the same problem : -

If ‘x’ was as big as ‘10^9’ , we could use Matrix exponentiation to solve the problem :slight_smile:

1 Like

Can you send me the link? I am thinking of participating this time :slight_smile:

1 Like

Very very thank you register here and inside it you will get codevita registrations

2 Likes

How you come to that realation… Can u give reason

I think this realtion is not correct for x=3 ans should be 3 but it gives 11… Or may be i calculated wrong?

1 Like

If ‘x’ is the question.
Answer is a(x-1).
So if x=3 is asked.
Answer is a(2).

Please give some explanation for that realation

Call a permutation bad if it is not good and call it ugly if it is good for exactly one index i. Let G(N), B(N), U(N) be the number of the good, the bad, and the ugly permutations of length N.

Given a bad permutation of length N, we obtain a permutation of length N−1by striking N off the sequence. The result is either bad or (if we started from …,x,N,x+1,……,x,N,x+1,…) it is ugly. In reverse, inserting N anywhere except after the N−1 in a bad permutation of length N−1 gives a bad permutation of length N, and so does inserting N between the only consecutive x and x+1 of an ugly permutation of length N−1. We conclude that

B(N)=(N−1)B(N−1)+U(N−1)

If from an ugly permutation with x followed by x+1, we strike the x+1and replace y by y−1 for all remaining y>x, we end up with a good permutation of length N−1 (note that x+1 cannot be followed by x+2 in the original ugly permutation). In reverse, from a good permutation, we can pick any x, replace all y>x with y+1 and then insert x+1 after the x to end up with an ugly permutation. We conclude that

NG(N−1)=U(N) …(2)

From (1) and (2) ,

B(N)+G(N)=N!B(N)+G(N)=N!

B(N)=(N−1)B(N−1)+(N−1)G(N−2)=(N−1)B(N−1)+(N−1)!−(N−1)B(N−2)

2 Likes

I don’t understand how you got the second equation. Could you explain it in a different way?
I think instead of

call it ugly if it is good for exactly one index

you mean

call it ugly if it is bad for exactly one index

Also your previous reply made me remember that the upper bound for maximum number of divisors upto n is 2 \sqrt n. So the recurrence I derived can be used to solve it too.

I gave him the recurrence equation as soon as he asked the question in my first reply.
Yes,I’ll edit the explanation part later when I get time :slight_smile:

1 Like

@kamalkarki03…here you go…https://codeforces.com/blog/entry/67706…in the comments you will get the link to the recursion relation and the explanation.

2 Likes

We’ve already posted the recurrence relation since the beginning. We were now interested in proving it. See the flow of the discussion properly. And why are you replying to me?

@karan …sorry brother i was not replying to you…it was a mistake…he asked for explanation …i just provided the link.

Thanks for the explanation @nitinsingh_945!

Also, @karangreat234 our recurrence relations are different. Mine is a 2-d recurrence relation while yours is a linear. I also remarked in my previous reply that you can still use mine to calculate the answer O(n) ( yours is O(\sqrt n) )

I never saw that :stuck_out_tongue: So sorry :slight_smile:

Aree nothing to be sorry bro :stuck_out_tongue:
I was thinking why everybody is posting the same formula again and again :grin: