### 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 = n_{k} p^{k} + n_{k-1} p^{k-1}

- . . + n
_{1}p + n_{0}.

Let base p representation of r be r = r_{k}p^{k}+ r_{k-1}p^{k-1} - . . + r
_{1}p + r_{0}.

Then C(n, r) p = (C(n<sub>k</sub>, r<sub>k</sub>) p) * . * . (C(n_{1}, r_{1}) 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(n_{0}, r_{0}) 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(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**

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 a_{r} a_{r-1}â€¦ a_{1} a_{0}

with no leading zeroes.

Let the ternary representation of k be b_{r} b_{r-1}â€¦ 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_{r-1}, b_{r-1}) * â€¦ * 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*

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(a_{r}, b_{r}) * 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 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

C(a_{L}a_{L - 1}â€¦a_{1}a_{0} , b_{L}b_{L - 1}â€¦b_{1}b_{0})

= 1 mod 3

For computing ans2(L) We are interested number of possible b_{L}b_{L - 1}â€¦b_{1}b_{0} such that

C(a_{L}a_{L - 1}â€¦a_{1}a_{0} , b_{L}b_{L - 1}â€¦b_{1}b_{0}) = 2 mod 3

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(L-1) and ans2(L) = ans2(L-1) 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.

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(a_{L}, b_{L})

will be 1.

If a_{L} is 2 we have three possible values for corresponding b_{L} 0, 1 and 2.

So we have ans1(L) = ans1(L-1)*2 + ans2(L-1)

for b_{L} = 0,2 we have C(a_{L}, b_{L}) = 1

for b_{L} = 1 we desire C(a_{L}, b_{L}) * C(a_{L - 1}â€¦a_{1}a_{0} ,

b_{L - 1}â€¦b_{1}b_{0}) = 1 mod 3 and hence we need

C(a_{L - 1}â€¦a_{1}a_{0} ,

b_{L - 1}â€¦b_{1}b_{0}) =

2 mod 3 since C(a_{L}, b_{L}) = 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 !!