### divyamsingal01's blog

By divyamsingal01, 8 months ago, So I did not find a tutorial for Maths section of CSES on codeforces, so thought of writing one.

I have put all my codes on https://github.com/div5252/CSES-Problem-Set.

This is now a complete tutorial, covering all the 21 questions of Mathematics Section of CSES.

1. Exponentiation

Tutorial
Code

2. Exponentiation II

Tutorial
Code

3. Counting Divisors

Tutorial
Code

4. Common Divisors

Tutorial
Code

5. Sum of divisors

Tutorial
Code

6. Binomial Coefficients

Tutorial
Code

7. Creating Strings

Tutorial
Code

8. Distributing Apples

Tutorial
Code

9. Christmas Party

Tutorial
Code

10. Fibonacci Numbers

Tutorial
Code

11. Throwing Dice

Tutorial
Code

12. Graph Paths I

Tutorial
Code

13. Graph Paths II

Tutorial
Code

14. Dice Probability

Tutorial
Code

15. Moving Robots

Tutorial
Code

16. Candy Lottery

Tutorial
Code

17. Inversion Probability

Tutorial
Code

18. Stick Game

Tutorial
Code

19. Nim Game I

Tutorial
Code

20. Nim Game II

Tutorial
Code

21. Stair Game

Tutorial
Code  Comments (29)
 » Thanks man...
 » Thanks a lot!
 » UPD: The tutorial is now complete. I have put the explanations and codes for all 21 problems.If you find any typo or any improvement in the explanation, please comment below.I haven't put the complete code(template portion) in the tutorial above, so as to prevent people for directly copying. Still if you wish to see the complete code, I have to the link to my github which contains AC solutions.
 » I still do not get sum of divisors :(
•  » » 8 months ago, # ^ | ← Rev. 2 →   link this might help, see the last answer
•  » » Yeah sorry, I have updated the explanation. I hope it is clear now.
•  » » » Thanks
 » THanks bro!
 » 7 months ago, # | ← Rev. 3 →   divyamsingal01 can you share the links to the editorials of other sections if you have found them?
•  » » 7 months ago, # ^ | ← Rev. 2 →
 » 7 months ago, # | ← Rev. 4 →   can you please verify if i understood moving robots correctly — for each robot we first get what is the probability for it to be on some i, j cell after k iterations.then for each cell what is the probability that it was empty after k iterns? — probability that robot 1 isnt there * probability that robot 2 isnt there and so on.... so we multiply the 1 — dp[i1][j1]now expectation — sum(P(xi)*xi) we calculated P(xi) and xi is 1?
 » 7 months ago, # | ← Rev. 2 →   For 21, here's a fairly straightforward proof:This game is essentially equivalent to Nim with a restricted number of additions permitted, with the piles being on the even indices, and the permitted additions being precisely the ones which can be done due to the shift from the pile on the immediate right (if it exists), with the only other possible move being removal of one element from an even pile at most a finite number of times, and thus this game is equivalent to vanilla Nim (proof here: https://cp-algorithms.com/game_theory/sprague-grundy-nim.html#toc-tgt-5), from where it is obvious.
 » divyamsingal01 can you pleaes elaborate on second problem Exponentiation II. I don't know much about Fermat's theorem.
•  » » fermat's theorm says that if a,m are coprime and m is prime. then pow(a,m-1)%m = 1.
 » Thankyou so much for the contribution
 » dardev cdes graph and yours math are the best!!
 » Would you care to explain the question Exponentiation II again? I tried to solve it using simple Binary exponentiation but got WA. I see you're using Fermat there what is the reason behind it. can we not solve it using simple Binary Exponentiation?
 » 6 months ago, # | ← Rev. 2 →   divyamsingal01In Graph Paths II, how did you decide the value of INF?I took INF=7e18 and it was giving WA, but on changing it to 4e18, it got Accepted!
•  » » You might be having long long overflow due to 7e18. Initialize, it sufficiently large so that it serves its purpose and encounters no overflow scenario.
 » Where can I find the proof of the recurrence relation in the "Throwing dice" editorial?
 » 4 months ago, # | ← Rev. 3 →   some additional explanation for Q-2 ,so we have a ^ b ^ calso note that m is a prime !from Fermat's little theorem we know a^ m-1 = 1 mod(m) for every prime mb^c = q*(m-1) + r where q and r are quotients and remainder resp ,a^(b^c) --> a^(q*(m-1)+r) --> a^q(m-1) * a^r = (1^q) * (a^r) mod(m)so our ans for a^b^c = a^r(mod m) where b^c = r mod(m-1)Hope it helps :-)
 » Mathematical Proof for Q21. It is a Staircase Nim Problem and can be easily proven that only even position value affects our answer. For the proof click here
 » Counting Necklaces How to get the inclusion/exclusion right?Can sombody explain with example n=12?
•  » » It's not that trivial if you don't know group theory, try reading about burnside's lemma.
•  » » » Found this which gives basically the solution. Link
•  » » » » If you would like to solve a similar problem on this theory , you may try this one https://codeforces.com/gym/101873/problem/B
 » Thanks a lot!
 » anyone solved grundy's game ?
 » Several weeks age CSES problem set presented some interesting new problems, including "Josephus Queries", https://cses.fi/problemset/task/2164 , and I'm looking forward to editorials for these new problems:)