PROBLEM LINK:
Author: Tuan Anh
Tester: Gedi Zheng
Editorialist: Praveen Vaka and Praveen Dhinwa
DIFFICULTY:
Medium - Hard
PREREQUISITES:
digit dp, Lucas theorem, combination formula.
PROBLEM:
Our aim is to find S(n) = sum C(n,k) mod 3 for all 0<=k<=n i.e., the sum of all entries in the nth row of modulo 3 pascal triangle.
We just need to output this value modulo 10^9+7
QUICK EXPLANATION:
You can use digit dynamic programming to solve the problem too. Using digit dp and information of lucas theorem, you can
maintain current combination C(n, k) modulo 3 as an extra state parameter.
Any number modulo 3 has to be one of {0, 1, 2}. Use Lucas’ Theorem to figure out the values of C(n, k) mod 3
EXPLANATION:
Notes and definitions
n is not a variable anywhere in this editorial it denotes the input value.
k is a variable which can take values between 0 and n inclusive.
S(n) is just the sum of the binomial coefficients modulo 3
but the value to be outputted is S(n) mod 10^9 + 7.
Note that C(n, k) is defined to be 0 when k > n.
Whenever we write a = b mod n we are denoting the congruence relation
Lucas’ theorem
In number theory, Lucas’s theorem expresses the remainder of division of the binomial coefficient C(n, r) by a
prime number p in terms of the base p expansions of the integers n and r.
Let base p representation of n be n = nk pk + nk-1 pk-1
- . . + n1 p + n0.
Let base p representation of r be r = rk pk + rk-1 pk-1 - . . + r1 p + r0.
Then C(n, r) p = (C(n<sub>k</sub>, r<sub>k</sub>) p) * . * . (C(n1, r1) p) * (C(n<sub>0</sub>, r<sub>0</sub>) p)
Digit Dynamic Programming Solution
You can visit the following link to learn digit dp. You can also see one of the editorials written by
me on the topic.
In this problem, we want to count number of numbers k from 0 to n having value of C(n, k) modulo 3, equal to some digit (0, 1 or 2).
Let me describe you a method to find out number of numbers k from 0 to n having value of C(n, k) modulo 3, equal to some digit, let us call
that digit needed. We can solve the problems of counting numbers from 0 to n having some property using digit dp.
Conceptually you can view digit dp as construction/ generation of numbers from most significant digit to least significant digit.
The main idea is that you don’t need to store/ remember the entire constructed number, instead you can only work by simply knowing a few
properties about the constructed number. eg. In our current problem, we don’t need to know the entire digits generated up to now.
Instead we need to store few useful information which is described below.
For applying Lucas’ theorem, we need to write the numbers in ternary representation.
Only thing that we need to store additionally in our dp state would be product of (C(n0, r0) p) * . * .
(C(n<sub>i - 1</sub>, r<sub>i - 1</sub>) p).
Whenever in the editorial we talk about first id digits, by that we mean the most significant first id digits.
Let dp[id][tight][val][needed] denote the number of numbers whose first id digit have been considered and tight denotes
whether the currently constructed number is equal or less than number formed by first id digits of n.
If tight is true, then it means that currently constructed number is equal to number constructed by first id digits in
ternary representation of N.
If tight is false, then it means that currently constructed number is less than number constructed by first id digits
in ternary representation of N.
val denotes the product of (C(nj, rj) % p) modulo 3 for all j from 0 to id - 1.
needed denotes what types of number we want to count. So we want to count number of numbers k from 0 to n having value of C(n, k) modulo
equal to needed.
Base Case
If id = number of digits in ternary representation of N, then we will check whether the val is equal to needed or not.
If val is equal to needed, then it means that this constructed number is valid. So we will add it to answer.
Transitions
We can consider following options for filling id th digit when we have already filled the first id - 1 digits.
If tight is true, then it means that our constructed number is still equal to number formed by first i digits of N.
Then we can try our current possible digit value from 0 to (id) th digit of N. If we try the digit more than id th digit,
then the constructed number will become greater than number formed by first id digits of N, which will violate the property that
our constructed number should be <= N.
After filling out this state, we will go to id + 1, hence new_i = id + 1.
If we take our current digit id to be strictly less than dig[i], then our new_tight will be false.
If we try out current digit x then new_val will be (val * C(i th digit of N, x)) % 3.
If tight is false, then it means that number constructed from first id - 1 digits has become less than number constructed from the
first id - 1 digit of N, So it means that our number can never exceed N, so we can chose the any digit from 0 to 3 and do the transitions
in the same way as explained in the previous paragraph.
Pseudo Code
List bits;
// Let bits store the ternary representation of n from MSB to LSB (
// ie. most significant bit to least significant bit.
long dp(int id, int tight, int val, int needed) {
if (memo[id][tight][val] != -1) { // used for memoization.
return memo[id][tight][val];
}
long res = 0;
if (id == bits.size()) {
if (val == needed) {
// if C(n, r) modulo 3 is equal to desired value,
// then it means the current generated number is valid and should be counted.
res = 1;
}
} else {
// tight denotes whether the number generated up to now is exactly equal to first id digits of r or not.
if (tight > 0) {
for (int i = 0; i < bits.get(id); i++) {
res += dp(id + 1, 0, (val * C(bits.get(id), i)) % 3, needed);
}
res += dp(id + 1, 1, (val * C(bits.get(id), bits.get(id))) % 3, needed);
} else {
for (int i = 0; i < 3; i++) {
res += dp(id + 1, 0, (val * C(bits.get(id), i)) % 3, needed);
}
}
}
// memoization
memo[id][tight][val] = res;
return res;
}
long ans = (dp(0, 1, 1, 1) + dp(0, 1, 1, 2) * 2) % mod;
Time Complexity
Number of states = Max value of id * max value of tight * max value of val = log(N) * 2 * 3.
Number of transitions = We are trying at most 3 numbers ie. 0, 1, or 2 for our current digit of k.
So overall time complexity will be around 18 log(N).
Another Solution
Input: a number n Output: a number S(n) % 10^9+7 getSum(n): n3 = getBase3(n) (x, y) = getOnesAndTwos(n3) return (x + 2 * y) % 109+7
Input: a number n
Output: a list of numbers each number is one among {0,1,2} and the list when read from left to right will be will be the base 3 representation of n
getBase3(n):
return the base 3 representation of n
Input: List L representing some number say n in ternary Output: a pair (x,y) where x is the number of of ones in nth row of the pascal triangle modulo 3 and y the number of twos in the same row getOnesAndTwos(L): if L is empty: return (1, 0) //The below base is not needed if we have the above one but added for clarity purpose if L has only one element d: if d is 0 return (1, 0) if d is 1 return (2, 0) if d is 2 return (2, 1) Let d be the first element of L Let L’ the list that we get by removing the first element from L (x’, y’) = getOnesAndTwos(L’) if d is 0 return (x’, y’) if d is 1 return (2*x’, 2*y’) if d is 2 return (2*x’+y’, x’+2*y’)
Explanation
C(n,k) mod 3 can only be one of the values 0, 1 and 2.
Let ans1 be the number of k’s for which C(n,k) = 1 mod 3
Let ans2 be the number of k’s for which C(n,k) = 2 mod 3
We will have S(n) = ans1 + 2 * ans2
Let us have a look at pascal triangle modulo 3.
0 - 1
1 - 1 1
2 - 1 2 1
3 - 1 0 0 1
4 - 1 1 0 1 1
5 - 1 2 1 1 2 1
6 - 1 0 0 2 0 0 1
7 - 1 1 0 2 2 0 1 1
8 - 1 2 1 2 1 2 1 2 1
9 - 1 0 0 0 0 0 0 0 0 1
For n = 8 we have ans1 = 5 and ans2 = 4 and hence S(8) = 5 * 1 + 4 * 2 = 13
We will use Lucas’ Theorem to find out the values of x and y for a given n.
For a fixed n and an arbitrary k let the ternary representation of n be ar ar-1… a1 a0
with no leading zeroes.
Let the ternary representation of k be br br-1… b1 b0 with leading zeroes
if needed to match up the length of ternary representation of n.
Note that r is fixed for a given n.
We have C(n, k) = C(ar, br) * C(ar-1, br-1) * … * C(a1, b) *
C(a0, b0) mod 3
We have C(n,k) = 0 mod 3 iff there exists at least one i such that C(ai, bi) = 0 the inequality
ai < bi will hold for that i.
We are interested in the k’s which result in a non zero value of C(n, k) mod 3 This will happen only when ai >= bi
for all i.
We can find the values of ans1 and ans2 by writing down a simple recursion.
Some notation first
Let f(x, l) denote suffix of length l+1 of the ternary representation of x
Under this notation we can rewrite the C(n, k) mod 3 as follows
C(n, k) = C(f(n, r), f(k, r)) % 3 = (C(ar, br) * C(f(n, r-1), f(k, r-1)) mod 3
To illustrate by an example
C(2101223, 1101213) = C(2, 1) * C(1, 1) * C(0, 0) * C(1, 1) * C(2, 2) * C(2, 1) mod 3
C(101223, 101213) = C(1, 1) * C(0, 0) * C(1, 1) * C(2, 2) * C(2, 1) mod 3
C(2101223, 1101213) = C(2, 1) * C(101223, 101213) mod 3
Let ans1(L) denote the number of entries with value 1 in f(n, L)th row of the pascal triangle modulo 3 and ans2(L)
denote the number of entries with value 2 in the same row.
f(n,L) is aLaL - 1…a1a0
For computing ans1(L) We are interested number of possible bLbL - 1…b1b0 such that
C(aLaL - 1…a1a0 , bLbL - 1…b1b0)
= 1 mod 3
For computing ans2(L) We are interested number of possible bLbL - 1…b1b0 such that
C(aLaL - 1…a1a0 , bLbL - 1…b1b0) = 2 mod 3
If aL is 0 we have to force the corresponding bL to be 0 otherwise C(aL, bL) would be 0.
So in this case we have ans1(L) = ans1(L-1) and ans2(L) = ans2(L-1) as there is only one way of choosing bL and that results in
C(aL, bL) to be 1.
If aL is 1 we have two possible values for corresponding bL 0 and 1.
So we have ans1(L) = ans1(L-1) * 2 and ans2(L) = ans2(L-1) * 2 as there are two ways of choosing bL and in both C(aL, bL)
will be 1.
If aL is 2 we have three possible values for corresponding bL 0, 1 and 2.
So we have ans1(L) = ans1(L-1)*2 + ans2(L-1)
for bL = 0,2 we have C(aL, bL) = 1
for bL = 1 we desire C(aL, bL) * C(aL - 1…a1a0 ,
bL - 1…b1b0) = 1 mod 3 and hence we need
C(aL - 1…a1a0 ,
bL - 1…b1b0) =
2 mod 3 since C(aL, bL) = 2
Similarly we have ans2(L) = ans1(L-1) + ans2(L-1)*2
We have S(n) = ans1® + 2 * ans2® where r is the the length of ternary representation of n.
One More Solution
Problems to Practice
Please add more problems for practice !!
(I didn’t try during the contest)