CSES Math Problemset Tutorial
NOTE : It is incomplete, If you don’t find what you’re looking for, check back in a week.
Table of Contents
So, there are total 31 problems, let’s solve them by the solve count.
Exponentiation⌗
Given and , calculate modulo . Standard application of binary exponentiation.
Exponentiation II⌗
Given , and , calculate modulo .
Is multiplied with itself times equal to ?
No, it is equal to , as exponents get added while multiplying.
Can be reduced further?
According to fermat’s little theorem , here being a prime integer.
So we can break down into some parts and an integer.
Therefore,
or
or
How to find now? After finding it becomes same as first problem.
is remainder is divided by .
Thus, it is equivalent to solving first problem twice, once raising to using as mod and then raising to using as mod. here is
Counting Divisors⌗
Count number of divisors of . There are about such queries in the largest test. It is trivial to find divisors of in , and it will be very slow here because of the large number of such queries.
One observation is that we have to just count the number of divisors not find the exact divisors.
Can we do some pre-processing and answer all queries in O(1) after that?
Let’s keep a vector where is number of divisors of . Any number will contribute to such that is multiple of .
So, if we update answer for multiples of by for every , will it be fast enough?
Number of steps for calculating answers up to is .
It is equal to
or
Therefore, it is fast enough to pre-process in and then answer queries in .
Common divisors⌗
Find a pair of numbers in given array such that they have maximum gcd.
Equivalent to finding greatest divisor which divides at least 2 numbers in the given array. We already know how to count divisors of a number in given range, as done in previous problem. Here we have to count multiples of numbers from to which exist in the given array, then print the largest number which has at least two multiples in the array.
Code is similar to the previous problem.
Sum of Divisors⌗
Given a number , calculate sum of all divisors of numbers in range to modulo .
In previous problem we did count how many times a divisor occurs for given numbers in an array. Now, let’s say our array has all the numbers in range . So once we get the frequency of all the divisors, it is a linear sum after that.
But, is too large to create an array and divisors will be very big too, obviously.
Unlike previous problem, all numbers from to are present here. Maybe this uniformity makes the problem easier for big .
Number of multiples of in range is .
Therefore, the answer to the problem for a given is
As can be as big as . We can’t calculate this sum in linear time directly.
Here are some observations:
- We can calculate first terms avoiding TLE verdict.
- After that takes only distinct values.
- When changes in range , then changes from to .
- is the largest value of for which is .
- All such that is continuous.
For an integer :
- is smallest value of such that
- is largest value of such that
- Contribution of the interval in where , can be written as:
Binomial Coefficients⌗
Many queries of the form and calculate modulo
calculate factorial and inverse factorial in advance and then answer all queries in .
Creating Strings II⌗
How many different strings can be formed from the characters of given string?
Here, using its characters means that all characters are to be used. So we have to print number of all valid permutations of given string.
Let’s suppose all characters are distinct in a string of length , then answer is . If characters are same out of then number of distinct permutations will be because after making characters same, we counted identical permutations times.
Distributing Apples⌗
Ways to distribute apples among children. It is possible that someone gets nothing. Consider partitions and apples are to be arranged together. Now every arrangement can be considered as a possible distribution. Apples to the left of partition are number of apples child gets, and number of apples to the right of last partition is the number of apples the last child gets.
It is equivalent to arranging characters of one type and characters of another type in a string. We just solved a similar problem above.
Christmas Party⌗
It is equivalent to finding how many ways are there such that a gift doesn’t leave with the same child it came to party with, and every gift can be with exactly one child. Therefore it is equal to counting the number of derangements of size .
Now there is a recurrence for counting derangements. Let’s say is number of derangements of size . Then
Consider gift at position we have choices to replace it with, suppose we replaced it with . After that either we can put at place of and then calculate , or we can put some other gift at place of and calculate .
Fibonacci Numbers⌗
Find fibonacci number, here can be as large as , so approach won’t work. Can be calculated by matrix exponentiation. Further reading on matrix exponentiation
Throwing Dice⌗
Ways to get sum by throwing a dice. Let’s say answer for is .
As we can only get the values in range , so these are the only penultimate states.
Here again can be as large as . It is similar to how we calculated fibonacci numbers, but with extra terms.
Graph Paths I⌗
Given a directed graph with nodes find out number of paths from node to with exactly edges.⌗
Adjacency matrix of an graph has an interesting property. When is adjacency matrix of a graph, then contains the number of paths of length from to .
You can see it is true when is . Adjacency matrix is essentially populated with number of paths of length between every pair of nodes.
How to be sure that it is true for higher powers?⌗
It can be proved by using principle of mathematical induction.
We know that it is true for
Suppose it is true for any , now is number of paths of length from to .
Let’s call number of paths of length from to as .
Every path from to of length will surely be extending a path of length by . Now from every intermediate node where path of length from ends, we need to find number of paths of length starting from and ending at . Therefore, we can write
Thus, is equal to multiplying and , more precisely .
To solve the problem, we’ll create an adjacency matrix for the given graph, call it and then print as the answer.
Graph Paths II⌗
In a weighted graph of nodes. Find the minimum path length from to with exactly edges.
It can be solved by using similar dp we used in the problem above.
Let’s say is minimum path length of edge path from to .
Then, we can write
Dice Probability⌗
What is the probability that sum of the outcomes of rolling a 6-faced dice times is in range ?
Let’s solve a simpler problem first.
What is the probability that sum of outcomes is , if we roll a dice times? As distance between and is very less we can add up answers to all the numbers between and .
Let be probability of getting sum in rolls.
So,
After calculating dp table, final answer of the problem will be
Bracket Sequences I⌗
Calculate the number of valid bracket sequences of length .
Here, the total length of the sequence is . So there won’t be any valid sequence when is odd because we’ll not have equal number of opening and closing brackets.
So what are the necessary and sufficient conditions to create a valid bracket sequence of length .
- Equal number of opening and closing brackets
- At every point number of closing brackets must be less than or equal to number of opening brackets.
Therefore after printing 0 for every odd , we needn’t care about first condition. Now, we have opening brackets and closing brackets and have to find number of valid bracket sequences using all of them.
Thus we have two kind of moves - Use or , and there is a limit on their use, each move can be used exactly times.
We can model this problem to an equivalent grid walking problem.
There is a grid (as shown in the figure below), you are standing at and the destination is , count total possible paths such that you can only move up i.e. use “” exactly times and move right i.e. use “” exactly times.

But, what about the condition that at every moment : can be rephrased as:
It means that no point in the possible valid paths will be above anti-diagonal. In the figures below, figure to the left shows a valid path, as it is entirely below the diagonal, and the figure to the left shows an invalid path as it overshoots diagonal at point .
How to count these good paths?
Total possible paths irrespective of the conditions imposed by the diagonal are So, if we can somehow count all the paths that overshoot the diagonal at some point, we can subtract them from total to get the count of good paths.
When a path crosses the diagonal for the first time, let’s call it move. Note that here is odd because it is the first time up moves become greater than right moves. Till move, we already have used exactly, right moves and up moves.
We are left with right moves and up moves.
PLEASE PAY ATTENTION NOW (MAGICAL STEP OF THE PROOF)
Now, for every move if we go up whenever the invalid path goes right and go right whenever the invalid path goes up, then sum of the moves in both directions becomes constant again.
What do we get by making the sum of moves constant?
It means that now any invalid path can be mapped to a path from to a fixed position in the grid, and we know how to calculate number of possible paths between two points in a grid, if we have only two kind of moves.
What is that fixed point?
In essence we swapped the number of right moves left and number of up moves left with each other.
By doing so,
And,
So final position every time would be , as shown in the figure below
Therefore number of such paths is

Therefore answer is
Bracket Sequences II⌗
Instead of just the number , you are also given a prefix of the sequence, how many valid ways are to complete this sequence such that it becomes a valid bracket sequence of length .
Let be number of opening brackets in the prefix and be number of closing brackets in the prefix.
Re-frame this problem to previously seen grid walking problem
You are standing at on the grid, how many ways are there to reach such that you always remain below the straight line connecting and .
So, , irrespective of any condition.
Again, all invalid paths can be mapped to paths from to
Thus,
First we check if the prefix is valid, i.e. it is under the diagonal, and number of opening brackets and closing brackets is less than .
If prefix is not valid, answer is .
else, it is