PROBLEM LINK:Author: Tuan Anh 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 Lucas' theorem Let base p representation of n be n = n_{k} p^{k} + n_{k1} p^{k1}
+ . . + n_{1} p + n_{0}. Then C(n, r) % p = (C(n_{k}, r_{k}) % p) * . * . (C(n_{1}, r_{1}) % p) * (C(n_{0}, r_{0}) % p) Digit Dynamic Programming SolutionYou 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 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(n_{0}, r_{0}) % p) * . * . (C(n_{i  1}, r_{i  1}) % 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(n_{j}, r_{j}) % 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 Transitions 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<integer> bits; // Let bits store the ternary representation of n from MSB to LSB ( // ie. most significant bit to least significant bit. Time Complexity Another SolutionInput: 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 Let us have a look at pascal triangle modulo 3. 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 a_{r} a_{r1}.... a_{1} a_{0} with no leading zeroes. Let the ternary representation of k be b_{r} b_{r1}.... b_{1} b_{0} 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(a_{r}, b_{r}) * C(a_{r1}, b_{r1}) * ..... * C(a_{1}, b_{}) * C(a_{0}, b_{0}) mod 3 We have C(n,k) = 0 mod 3 iff there exists at least one i such that C(a_{i}, b_{i}) = 0 the inequality a_{i} < b_{i} 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 a_{i} >= b_{i} for all i. We can find the values of ans1 and ans2 by writing down a simple recursion. Some notation first Under this notation we can rewrite the C(n, k) mod 3 as follows To illustrate by an example 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 a_{L}a_{L  1}....a_{1}a_{0} For computing ans1(L) We are interested number of possible b_{L}b_{L  1}....b_{1}b_{0} such that For computing ans2(L) We are interested number of possible b_{L}b_{L  1}....b_{1}b_{0} such that If a_{L} is 0 we have to force the corresponding b_{L} to be 0 otherwise C(a_{L}, b_{L}) would be 0. So in this case we have ans1(L) = ans1(L1) and ans2(L) = ans2(L1) as there is only one way of choosing b_{L} and that results in C(a_{L}, b_{L}) to be 1. If a_{L} is 1 we have two possible values for corresponding b_{L} 0 and 1. If a_{L} is 2 we have three possible values for corresponding b_{L} 0, 1 and 2. Similarly we have ans2(L) = ans1(L1) + ans2(L1)*2 We have S(n) = ans1(r) + 2 * ans2(r) where r is the the length of ternary representation of n. One More SolutionProblems to Practice
Please add more problems for practice !! AUTHOR'S, TESTER'S and Editorialist's SOLUTIONS:
This question is marked "community wiki".
asked 28 Dec '14, 14:01
showing 5 of 6
show all

This problem can be easily solved using oeis.org! answered 28 Dec '14, 16:00
Really  http://oeis.org/A051638 :( (I didn't try during the contest)
(28 Dec '14, 16:13)
Hey @lord_f
(28 Dec '14, 16:24)
2
You simply generate few elements from sequence (found by brute force for example) and enter those in "search" field separated by commas (
(28 Dec '14, 16:41)
what you do after getting the sequense
(09 Jan '15, 01:26)

Very nice problem ;) answered 28 Dec '14, 14:03
yes indeed :)
(28 Dec '14, 14:37)
hey @betlista can u help me why my code is giving WA with the 3rd subtask, though am following he digit dp formulation along with lucas theorem , below is the link to my solution http://www.codechef.com/viewsolution/5663087
(28 Dec '14, 16:17)

Good problem, loved solving it ^_^ answered 28 Dec '14, 14:42

How about this approach? for any n > 5 whenever we have more than 3 numbers in numerator then ans is always going to be zero (Any 3 continuous numbers such that x * (x + 1) * (x + 2) are always divisible by 3) Then we only have to calculate for those nCr values where on numerator only 1 or 2 numbers There may be something wrong with this approach! just wanted to share! answered 28 Dec '14, 19:03

@dpraveen why are we not calculating dp(0,1,1,0) ?? because we need 0 digit also ,and why there is 2*dp(0,1,1,2) ?? got it sorry my mistake in understanding :'(
@adijimmy: Because what we need is the sum of (C(n, k) % 3) for k = 0 to n. In our case, Let ans_needed denotes number of k's having (C(n, k) % 3 = needed). So our desired answer will be 0 * ans_0 + 1 * ans_1 + 2 * ans_2. So it will ans_1 + 2 * ans_2. This is the precise reason for multiplying dp(0,1,1, 2) by 2.
@dpraveen thanks for such a great editorial :)
@adijimmy: welcome :)
"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 "
what does f(n,L)th row refer to here? f(n,L) was defined as the suffix of length l+1 of the base 3 representation of N.
@ironmandhruv f(N, L) is value of aLaL  1....a1a0.