Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### divyamsingal01's blog

By divyamsingal01, 13 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 tutorial covers 29 questions of Mathematics Section of CSES.

1. Josephus Queries

Tutorial
Code

2. Exponentiation

Tutorial
Code

3. Exponentiation II

Tutorial
Code

4. Counting Divisors

Tutorial
Code

5. Common Divisors

Tutorial
Code

6. Sum of divisors

Tutorial
Code

7. Divisor Analysis

Tutorial
Code

8. Prime Multiples

Tutorial
Code

9. Counting Coprime Pairs

Tutorial
Code

10. Binomial Coefficients

Tutorial
Code

11. Creating Strings II

Tutorial
Code

12. Distributing Apples

Tutorial
Code

13. Christmas Party

Tutorial
Code

14. Bracket Sequences I

Tutorial
Code

15. Bracket Sequences II

Tutorial
Code

16. Counting Necklaces

Tutorial
Code

17. Counting Grids

18. Fibonacci Numbers

Tutorial
Code

19. Throwing Dice

Tutorial
Code

20. Graph Paths I

Tutorial
Code

21. Graph Paths II

Tutorial
Code

22. Dice Probability

Tutorial
Code

23. Moving Robots

Tutorial
Code

24. Candy Lottery

Tutorial
Code

25. Inversion Probability

Tutorial
Code

26. Stick Game

Tutorial
Code

27. Nim Game I

Tutorial
Code

28. Nim Game II

Tutorial
Code

29. Stair Game

Tutorial
Code

30. Grundy's Game

Tutorial
Code

31. Another Game

UPD: I have also added tutorials for the newly added problems in Maths section. I am yet to do two problems — Counting Grids and Another Game. It would be helpful if someone could come up with tutorials for these.

• +92

 » 13 months ago, # |   +5 Thanks man...
 » 13 months ago, # |   +5 Thanks a lot!
 » 13 months ago, # |   +3 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.
 » 13 months ago, # |   +1 I still do not get sum of divisors :(
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 link this might help, see the last answer
•  » » 13 months ago, # ^ |   0 Yeah sorry, I have updated the explanation. I hope it is clear now.
•  » » » 12 months ago, # ^ |   0 Thanks
 » 13 months ago, # |   0 THanks bro!
 » 13 months ago, # | ← Rev. 3 →   0 divyamsingal01 can you share the links to the editorials of other sections if you have found them?
•  » » 13 months ago, # ^ | ← Rev. 2 →   0
 » 13 months ago, # | ← Rev. 4 →   0 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?
 » 13 months ago, # | ← Rev. 2 →   +3 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.
 » 12 months ago, # |   0 divyamsingal01 can you pleaes elaborate on second problem Exponentiation II. I don't know much about Fermat's theorem.
•  » » 12 months ago, # ^ |   0 fermat's theorm says that if a,m are coprime and m is prime. then pow(a,m-1)%m = 1.
 » 12 months ago, # |   0 Thankyou so much for the contribution
 » 12 months ago, # |   0 dardev cdes graph and yours math are the best!!
 » 11 months ago, # |   0 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?
 » 11 months ago, # | ← Rev. 2 →   0 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!
•  » » 9 months ago, # ^ |   0 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.
 » 9 months ago, # |   0 Where can I find the proof of the recurrence relation in the "Throwing dice" editorial?
 » 9 months ago, # | ← Rev. 3 →   0 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 :-)
 » 9 months ago, # |   +3 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
 » 7 months ago, # |   +6 Counting Necklaces How to get the inclusion/exclusion right?Can sombody explain with example n=12?
•  » » 7 months ago, # ^ |   +6 It's not that trivial if you don't know group theory, try reading about burnside's lemma.
•  » » » 7 months ago, # ^ |   +6 Found this which gives basically the solution. Link
•  » » » » 7 months ago, # ^ |   +3 If you would like to solve a similar problem on this theory , you may try this one https://codeforces.com/gym/101873/problem/B
 » 7 months ago, # |   0 Thanks a lot!
 » 7 months ago, # |   0 anyone solved grundy's game ?
 » 7 months ago, # |   0 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:)
 » 5 months ago, # | ← Rev. 2 →   0 Great Tutorial. I had a doubt in CSES Prime Multiples.This is my codeReference From CP-AlgoThis is more related to C++ data types. So when I use long long for variable mult the output is wrong and when I use double the output is correct. What is the reason behind this ? One Example of Output input1000000000000000000 202 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71correct output 872202319624080142user output 872202319624079358
 » 4 months ago, # |   0 ans*=1e6 ans=round(ans); ans/=1e6;My question is , why did you use this rounding code for Dice probability question and not for other questions like Inversion Probability , Moving Robots etc
 » 4 months ago, # |   0 In exponentiation II , why we use fermat's theorem ? Can't we just find x = power(b,c) and then power(a,x) ? I tried but it didn't work. So I want to know why? Note : I am not from Maths background so if you will share any resources it will be very useful.
•  » » 4 months ago, # ^ |   0 That's because $b^c$ will overflow (doesn't fit in long long), so we used Fermat's Theorem.
 » 3 months ago, # |   0 Thanks a lot!!
 » 3 months ago, # |   0 Hi In COUNTING DIVISORS (problem-4), I understand that an array of 0s is created and then each 0 in the array is incremented in the for-loops.I want to know the rationale behind this. Why this works?
•  » » 3 months ago, # ^ | ← Rev. 3 →   0 Explained it here
•  » » » 3 months ago, # ^ |   0 Nicely explained. Understood the logic. :)
 » 7 weeks ago, # |   +3 For Another Game, the first player wins iff there is at least one heap with an odd number of coins.If all heaps have an even number of coins, the second player can win, by taking coins from the same set of piles as the first player on the previous turn. This ensures that all heaps have an even number of piles at the end of the second player's turn, so the strategy can continue.If at least one heap has an odd number of coins, the first player can win by taking one coin from each pile with an odd number of coins, reducing the game to the first scenario.Proof of Stair Game is as follows:Consider the nim game on the even-numbered piles. If the first player wins this game, they can win the entire game. A valid strategy: In the first move, play in the even-numbered piles with an optimal nim strategy. In subsequent moves: If the second player moves coins from an odd-numbered pile $p$ to pile $p-1$, the first player should move the same number of coins from $p-1$ to $p-2$. Note that the nim game on the even-numbered piles is unaffected, and it is impossible for the first player to lose during this. If the second player moves coins from an even-numbered pile, they have effectively made a move in the nim game, so the first player's next move should be to play an optimal move in the nim game. After all the moves in the nim game have been exhausted, we know that the second player has the next move and that all coins are in odd-numbered piles, which means the first player ultimately wins using this strategy.If the second player wins the nim game, use a similar strategy as the one above (i.e. if first player plays on odd-numbered pile, mirror their move; if they play on even-numbered pile, play nim game).
 » 7 weeks ago, # |   +3
 » 4 weeks ago, # |   +1 17. Counting Grids TutorialWe will use Burnside's Lemma. Define a group of rotations $G = { 0^\circ, 90^\circ, 180^\circ, 270^\circ }$ that will act upon $X$ which we define as the set of all possible square grids with side length $n$. Burnside's Lemma states that $|X / G| = \frac 1 {|G|} \sum_{g \in G} |X^g|$Thus, it suffices to find the number of grids that remain the same after a rotation of $g$ degrees for each $g$ in $G$. For $g = 0^\circ$, all grids will remain unchanged after a rotation of $0^\circ$. Thus, the number of grids that satisfy this property is $2^{n^2}$ For $g = 90^\circ$, we see that a given square will form a cycle of period 4 (excluding the middle square in the case where $n$ is odd). Because all squares in the cycle must be the same color, there is $2 ^ {n^2 / 4}$ ways to do this for even $n$ and $2 ^ {\frac {n^2 - 1} 4} \cdot 2$ for odd $n$ (the second $\cdot 2$ comes from the fact that the middle square can be one of two colors). For $g = 180^\circ$, we see that a given square will form a cycle of period 2 (excluding the middle square in the case where $n$ is odd). Thus, there is $2 ^ {n^2 / 2}$ ways to do this for even $n$ and $2 ^ {\frac {n^2 - 1} 2} \cdot 2$ for odd $n$. For $g = 270^\circ$, the answer is the same as $g = 90^\circ$ (this is simply a $90^\circ$ in the opposite direction) The final answer is simply the sum of the four values divided by 4 (or in this case, multiplied $4^{-1} \mod 1000000007 = 250000002$ Code#include using namespace std; using ll = long long; const ll MOD = 1e9 + 7; ll fast_pow(ll a, ll b) { ll res = 1; for (a %= MOD; b; b >>= 1) { if (b & 1) res = res * a % MOD; a = a * a % MOD; } return res; } ll N; int main() { cin >> N; ll a = fast_pow(2, N * N); ll b = (N % 2 == 0 ? fast_pow(2, N * N / 4) : fast_pow(2, (N * N - 1) / 4) * 2 % MOD); ll c = (N % 2 == 0 ? fast_pow(2, N * N / 2) : fast_pow(2, N * (N - 1) / 2) * fast_pow(2, N / 2 + 1) % MOD); ll d = b; cout << (a + b + c + d) % MOD * 250000002 % MOD << '\n'; } (Sorry for the Necropost)
•  » » 7 days ago, # ^ | ← Rev. 2 →   0 in case someone is wondering how to get $250000002$ without using online calculator Code#include using namespace std; int extended_euclidean(int a, int b, int &x, int &y) { if(a == 0) { x = 0, y = 1; return b; } int x1, y1, d = extended_euclidean(b % a, a, x1, y1); x = y1 - (b / a) * x1, y = x1; return d; } int modular_inverse(int a, int m) { int x, y; int g = extended_euclidean(a, m, x, y); if (g != 1) return -1; else { x = (x % m + m) % m; return x; } } long long mod_pow(long long base, long long exp, long long mod) { long long res = 1; while (exp > 0) { if (exp & 1) res = (res * base) % mod; base = (base * base) % mod; exp >>= 1; } return res; } const int M = 1e9 + 7; const int G = 4; void solve() { long long N; cin >> N; long long deg0 = mod_pow(2, N * N, M); long long deg90 = (N & 1 ? mod_pow(2, (N * N - 1) / 4, M) * 2 : mod_pow(2, N * N / 4, M)) % M; long long deg180 = (N & 1 ? mod_pow(2, (N * N - 1) / 2, M) * 2 : mod_pow(2, N * N / 2, M)) % M; long long deg270 = deg90; long long ans = (deg0 + deg90 + deg180 + deg270) % M; (ans *= modular_inverse(G, M)) %= M; cout << ans << endl; } int main() { ios_base::sync_with_stdio(false), cin.tie(nullptr); // int T; cin >> T; // while(T--) solve(); solve(); return 0; } 
•  » » » 7 days ago, # ^ |   0 Wolfram Alpha works perfectly well
 » 3 weeks ago, # |   0 Can someone explain the inverse function in editorial?